拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
拓扑排序算法模板
c++版本
1
待填。。。。
课程表(中等)
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？课程表
思路：本题可约化为：课程安排图是否是有向无环图(DAG)。即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
/**
* 广度优先搜索， 拓扑排序
* 1.统计课程安排图中每个结点的入度，生成入度表
* 2.借助一个队列，将所有入度为0的结点入队
* 3.当队列非空的时候，依次将队首节点出队，在课程安排表中删除此结点
* (不是真正删除此节点，而是将此节点对应的所有邻接结点的入度减一，如果减一后邻接结点的入度为0，
* 说明该节点的课程可以学习，则将该节点入队)。
* 4.每次队列出队时，即当前课程已修完，课程总数减一，最后通过剩余课程是否是0来判断是否可以修完课程
*
*/
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> indegree(numCourses); // 统计每门课程的入度
vector<vector<int>> adj(numCourses); // 邻接表
queue<int> q; // 队列
// 统计入度以及构建邻接表
for (auto c : prerequisites) {
indegree[c[0]]++;
adj[c[1]].push_back(c[0]);
}
// 将入度为0的课程结点入队
for (int i = 0; i < numCourses; i++)
if (indegree[i] == 0) q.push(i);
while (q.size()) {
int pre = q.front(); // 当前课程出队
q.pop();
numCourses--; // 剩余课程减一
// 与当前结点相邻的结点的入度减一
for (auto c : adj[pre])
// 如果相邻结点的入度减一之后等于0，说明该节点的课程可以修，该节点入队
if (--indegree[c] == 0) q.push(c);
}
// 最后判断能否修完所有课程
return numCourses == 0;
}
/**
* 深度优先 判断有向图中是否有环
* 1.借助一个标志列表flag，用于判断每个结点(课程)的状态：
* (1)未被访问 i=0;
* (2)已被其他节点启动的dfs访问 i=-1; 已经访问过了
* (3)已被当前结点启动的dfs访问 i=1; 正在访问
* 2.对课程的每个结点依次执行dfs，判断每个结点起步的dfs是否有环，若有环直接返回false
* (1)终止条件：flag[i]=-1,说明当前结点已被其他结点启动的dfs访问，无需重复搜索，直接返回true。flag[i]=1说明在本轮dfs搜索中i被第2次搜索，说明有环，直接返回false。
* (2)将当前访问的结点的标记置为1，即标记其被本轮dfs访问。
* (3)递归访问当前节点i的所有邻接节点j，当发现环直接返回 False
* (4)当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点flag置为−1并返回True。
*/
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> flag(numCourses);
for (auto c : prerequisites) adj[c[1]].push_back(c[0]); //构建邻接表
for (int i = 0; i < numCourses; i++) { // 从每个课程结点开始遍历
if (!dfs(adj, flag, i)) return false;
}
return true;
}
bool dfs(vector<vector<int>>& adj, vector<int>& flag, int i) {
if (flag[i] == 1) return false;
if (flag[i] == -1) return true;
flag[i] = 1; // 将当前访问的结点的标记置为1，即标记其被本轮dfs访问
// 递归遍历当前结点的邻接结点
for (auto c : adj[i]) {
if (!dfs(adj, flag, c)) return false;
}
flag[i] = -1; // 当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点flag置为−1
return true;
}
};
课程表II(中等)
现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。课程表II
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
/**
* 广度优先搜索
* 1.统计课程安排图中每个结点的入度，生成入度表
* 2.借助一个队列，将所有入度为0的结点入队
* 3.当队列非空的时候，依次将队首节点出队，在课程安排表中删除此结点
* (不是真正删除此节点，而是将此节点对应的所有邻接结点的入度减一，如果减一后邻接结点的入度为0，
* 说明该节点的课程可以学习，则将该节点入队)。
* 4.每次队列出队时，即当前课程已修完，课程总数减一，最后通过剩余课程是否是0来判断是否可以修完课程
*/
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> indegree(numCourses); // 统计没门课程的入度
vector<vector<int>> adj(numCourses); // 邻接表
queue<int> q; // 队列 用于广度优先搜索
for (auto c : prerequisites) { // 统计每个结点的入度，并构建邻接表
indegree[c[0]]++;
adj[c[1]].push_back(c[0]);
}
for (int i = 0; i < numCourses; i++) // 将入度为0的结点入队进行遍历
if (indegree[i] == 0) q.push(i);
vector<int> res; // 记录答案
while (q.size()) {
int pre = q.front(); // 休当前课程
q.pop();
res.push_back(pre);
numCourses--; // 课程数量减一
for (auto c : adj[pre]) // 更新与当前课程相连的结点的入度
if (--indegree[c] == 0) q.push(c); // 如果入度为0说明可以修了
}
if (numCourses == 0) return res;
return {};
}
vector<int> res;
/**
* 深度优先 判断有向图中是否有环
* 1.借助一个标志列表flag，用于判断每个结点(课程)的状态：
* (1)未被访问 i=0;
* (2)已被其他节点启动的dfs访问 i=-1;
* (3)已被当前结点启动的dfs访问 i=1;
* 2.对课程的每个结点依次执行dfs，判断每个结点起步的dfs是否有环，若有环直接返回false
* (1)终止条件：flag[i]=-1,说明当前结点已被其他结点启动的dfs访问，无需重复搜索，直接返回true。flag[i]=1说明在本轮dfs搜索中i被第2次搜索，说明有环，直接返回false。
* (2)将当前访问的结点的标记置为1，即标记其被本轮dfs访问。
* (3)递归访问当前节点i的所有邻接节点j，当发现环直接返回 False
* (4)当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点flag置为−1并返回True。
*/
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> flag(numCourses);
for (auto c : prerequisites) adj[c[1]].push_back(c[0]); //构建邻接表
for (int i = 0; i < numCourses; i++) // 从每个课程结点开始遍历
if (dfs(i, adj, flag)) return {};
reverse(res.begin(), res.end()); // 翻转一下
return res;
}
bool dfs(int i, vector<vector<int>>& adj, vector<int>& flag) {
if (flag[i] == 1) return true; // 说明有环
if (flag[i] == -1) return false;
flag[i] = 1;
for (auto c : adj[i])
if (dfs(c, adj, flag)) return true;
res.push_back(i); // 先存入进去的是最后遍历的，所以最后需要翻转一下
flag[i] = -1;
return false;
}
};
项目管理(困难)
公司共有 n 个项目和 m 个小组，每个项目要不没有归属，要不就由其中的一个小组负责。我们用 group[i] 代表第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：同一小组的项目，排序后在列表中彼此相邻。项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
结果要求：如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表。项目管理
参考代码
1
没看。。。
