
拓扑排序是在一个有向无环图(Directed Acyclic Graph, DAG)中对顶点的排序, 每个有向无环图可以有一个或者多个拓扑排序. 若图中存在环, 则无法进行排序, 因为环上的两点 (v, w) 相互依赖, 即 v 先于 w, w 也先于 v.
基本概念
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。
为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。
通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称 AOV 网。
维基百科
在计算机科学领域，有向图的拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边uv，u 在排序中都在 v 之前。
例如，图形的顶点可以表示要执行的任务，有向边可以表示一个任务必须在另一个任务之前执行的约束; 在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有循环时，即如果它是有向无环图，则拓扑排序是可能的。 任何 DAG 具有至少一个拓扑排序，并且已知这些算法用于在线性时间内构建任何 DAG 的拓扑排序。
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个 拓扑排序(Topological sorting)
- 每个顶点出现且只出现一次；
- 若A在序列中排在B的前面，则在图中不存在从 B 到 A 的路径。
拓扑排序算法
由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下几步，直到不存在入度为 0 的顶点为止。
- 初始时, 计算所有顶点的 (color{blue}{入度}), 使用队列记录入度为 0 的顶点
- 选择一个入度为 0 的顶点出发, 因为这些顶点没有任何先决条件
- 从网中删除此顶点及所有出边, 更新剩余节点的入度, 并使用队列跟踪入度为 0 的顶点
- 重复2, 3步骤, 直到队列为空
循环结束后，若输出的顶点数小于网中的顶点数，则说明图中有环路，否则输出的顶点序列就是一种拓扑序列
当使用邻接链表时, 拓扑排序的时间复杂度为 O(|E|+|V|)
拓扑排序的应用
- 课程选修的先决条件
- 检测死锁
- 计算作业的流水线
- 解析电子表格中的公式
Course Schedule
您必须参加总共 n 门课程，标记为 0 ~ n-1. 有些课程可能有先决条件，例如要修课程 0，你必须先修课程 1，表示为一对元组：[0, 1], 您可以假设输入先决条件中没有重复的边。
鉴于课程总数和先决条件对列表，您是否可以完成所有课程？
example
Input: 2, [[1, 0]]
Output: true
Input: 2, [[1, 0], [0, 1]]
Output: false
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> indegrees(numCourses, 0); // 入度
unordered_map<int, vector<int>> adjList; // 邻接链表
queue<int> zeroIndegrees; // 记录入度为0的顶点
vector<int> topoSortVertexs; // 拓扑排序的线性序列
for (auto pres : prerequisites) {
indegrees[pres.first]++; // (first, second), second 为先决条件
adjList[pres.second].push_back(pres.first);
}
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] == 0) {
zeroIndegrees.push(i);
}
}
while (!zeroIndegrees.empty()) {
int vertex = zeroIndegrees.front();
zeroIndegrees.pop();
topoSortVertexs.push_back(vertex);
for (auto son : adjList[vertex]) {
indegrees[son]--;
if (indegrees[son] == 0) {
zeroIndegrees.push(son);
}
}
}
return topoSortVertexs.size() == numCourses;
}
};
(leetcode 207)