介绍
拓扑排序（Topological Sorting）是一种常用的排序算法，它是对有向无环图（DAG, Directed Acyclic Graph）的一种排序方法。
应用
拓扑排序在许多领域都有重要的应用。
拓扑排序可以用于： 检测有向环：如果一个有向图无法进行拓扑排序，说明该图中存在有向环。因此，拓扑排序可以用于检测有向图中是否存在环，这在许多图算法和问题中都有重要的应用。 最短路径和关键路径分析：在有向无环图中，拓扑排序可以与其他算法结合使用，来求解最短路径问题和关键路径问题。例如，在关键路径法（CPM）中，拓扑排序可以用于确定项目中的关键任务，从而帮助项目管理者合理安排资源，缩短项目工期。 图的遍历和搜索：拓扑排序可以作为图遍历和搜索算法的预处理步骤，例如在深度优先搜索（DFS）中，拓扑排序可以帮助确定搜索的顺序，提高搜索效率。
拓扑排序的顺序可能不只一种。
算法原理
- 在图中找到所有入度为0的点
- 把所有入度为0的点在图中删掉，重点是删除影响！继续找到入度为0的点并删掉影响
- 直到所有点都被删掉，依次删除的顺序就是正确的拓扑排序结果
- 如果能够删除所有的点(拓扑排序结果包含所有节点)，说明有向图里没有环；否则说明有环
算法步骤
- 建立邻接表，记录每个结点的入度
- 初始化入度为0的队列
- 循环队列，每次取出一个入度为0的结点，将其放入拓扑排序结果，并将其所有邻接点的入度减1，如果入度减1后变为0，则将邻接点入队列
- 循环结束后，如果拓扑排序结果包含所有结点，则说明无环；否则说明有环
代码实现
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
int main(){
int n;
cin >> n;
vector<int> inDegree(n + 10, 0); // 记录每个结点的入度
queue<int> q; // 队列记录入度为0的结点
vector<int> topoSort; // 拓扑排序结果
vector<int> g[n + 10]; // 邻接表
for(int i = 1; i <= n; i++){ // 建图并记录入度
int uu, vv;
cin >> uu >> vv;
g[uu].push_back(vv); // 建立邻接表
inDegree[vv]++; // 记录每个结点的入度
}
for(int i = 1; i <= n; i++){ // 初始化入度为0的队列
if(inDegree[i] == 0){
q.push(i); // 入度为0的结点入队列
}
}
while(!q.empty()){
int u = q.front();
q.pop();
topoSort.push_back(u); // 拓扑排序结果
for(int v : g[u]){
inDegree[v]--; // 减少每个邻接点的入度
if(inDegree[v] == 0){
q.push(v); // 入度为0的邻接点入队列
}
}
}
if(topoSort.size() == n){ // 判断是否有环
cout << "No" << endl; // 无环
}else{
cout << "Yes" << endl; // 有环
}
for(int u : topoSort){
cout << u << " "; // 输出拓扑排序结果
}
return 0;
}
