本课时有配套视频讲解，购买后即可观看（永久有效）
拓扑排序
一、课上练习
编程练习
二、知识总结
✨ 核心思想
拓扑排序是针对有向无环图（Directed Acyclic Graph，简称 DAG）的顶点的一种排序方法，其目的是对图中所有顶点进行线性排序，使得对于任何一条有向边 u→v，顶点 u 都在顶点 v 之前。拓扑排序不是唯一的，一个图可能有多个合法的拓扑排序结果。
✨ 应用场景
拓扑排序通常用于处理具有依赖关系的任务规划问题，例如：
- 任务调度：在构建系统或项目管理中，一些任务必须在其他任务完成后才能开始。
- 课程规划：学生选课系统中，一些课程有先决条件，必须先完成某些课程才能选修其他课程。
- 解析表达式：在编译器中，解析变量的声明依赖关系。
✨ Kahn 算法
Kahn 算法是一个迭代过程，它通过选择没有入边的顶点，然后移除该顶点及其所有出边来逐步构建拓扑排序。
算法步骤：
- 统计所有顶点的入度（指向该顶点的边的数量）。
- 将所有入度为 0 的顶点放入一个队列中。
- 从队列中取出一个顶点，将其添加到排序结果中，然后减少其所有邻接点的入度。
- 如果邻接点的入度变为 0，则将其加入队列。
- 重复步骤 3 和 4，直到队列为空。
- 如果排序结果中的顶点数量少于图中的顶点总数，则图中存在环，无法进行拓扑排序。
下面的代码演示了 Kahn 算法的实现方式：
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <list>
5using namespace std;
6
7// 函数用于进行Kahn算法的拓扑排序
8void topologicalSortKahn(vector<list<int>>& graph, int numVertices) {
9 vector<int> inDegree(numVertices, 0); // 存储每个顶点的入度
10 queue<int> zeroInDegree; // 存储入度为0的顶点的队列
11 vector<int> topOrder; // 存储拓扑排序的结果
12
13 // 计算所有顶点的入度
14 for (int i = 0; i < numVertices; ++i) {
15 for (int vertex : graph[i]) {
16 inDegree[vertex]++;
17 }
18 }
19
20 // 将所有入度为0的顶点加入队列
21 for (int i = 0; i < numVertices; ++i) {
22 if (inDegree[i] == 0) {
23 zeroInDegree.push(i);
24 }
25 }
26
27 // 进行拓扑排序
28 while (!zeroInDegree.empty()) {
29 int u = zeroInDegree.front(); // 从队列中取出一个顶点
30 zeroInDegree.pop();
31 topOrder.push_back(u); // 加入拓扑排序结果中
32
33 // 遍历当前顶点的所有邻接顶点
34 for (int neighbor : graph[u]) {
35 // 将这些邻接顶点的入度减1
36 if (--inDegree[neighbor] == 0) {
37 zeroInDegree.push(neighbor); // 如果入度变为0，则加入队列
38 }
39 }
40 }
41
42 // 检查是否有环（如果排序结果中的顶点数量不等于图中的顶点总数）
43 if (topOrder.size() != numVertices) {
44 cout << "There is a cycle in the graph." << endl;
45 } else {
46 cout << "Topological Order:";
47 for (int v : topOrder) {
48 cout << v << " ";
49 }
50 cout << endl;
51 }
52}
53
54int main() {
55 // 顶点数
56 int numVertices = 6;
57 // 图的邻接表表示
58 vector<list<int>> graph(numVertices);
59 // 添加边，构造图
60 graph[5].push_back(2);
61 graph[5].push_back(0);
62 graph[4].push_back(0);
63 graph[4].push_back(1);
64 graph[2].push_back(3);
65 graph[3].push_back(1);
66 // 调用拓扑排序函数
67 topologicalSortKahn(graph, numVertices);
68
69 return 0;
70}✨ 执行示例
以下面这个有向图为例，追踪 Kahn 算法的完整执行过程：
图的边：5→2, 5→0, 4→0, 4→1, 2→3, 3→1
顶点：0, 1, 2, 3, 4, 5第 1 步：计算所有顶点的入度
| 顶点 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 入度 | 2 | 2 | 1 | 1 | 0 | 0 |
第 2 步：将入度为 0 的顶点加入队列
队列：[4, 5]，结果：[]
第 3 步：取出顶点 4，处理其邻接点
- 取出 4，结果：[4]
- 4→0：顶点 0 入度 2→1
- 4→1：顶点 1 入度 2→1
- 队列：[5]
第 4 步：取出顶点 5，处理其邻接点
- 取出 5，结果：[4, 5]
- 5→2：顶点 2 入度 1→0，加入队列
- 5→0：顶点 0 入度 1→0，加入队列
- 队列：[2, 0]
第 5 步：取出顶点 2，处理其邻接点
- 取出 2，结果：[4, 5, 2]
- 2→3：顶点 3 入度 1→0，加入队列
- 队列：[0, 3]
第 6 步：取出顶点 0
- 取出 0，结果：[4, 5, 2, 0]
- 顶点 0 没有出边
- 队列：[3]
第 7 步：取出顶点 3，处理其邻接点
- 取出 3，结果：[4, 5, 2, 0, 3]
- 3→1：顶点 1 入度 1→0，加入队列
- 队列：[1]
第 8 步：取出顶点 1
- 取出 1，结果：[4, 5, 2, 0, 3, 1]
- 队列为空，算法结束
最终拓扑排序结果：4 5 2 0 3 1
排序结果包含 6 个顶点，等于图的总顶点数，说明图中没有环。
✨ 解题步骤详解
例题：判断课程安排是否可行
某学校有 4 门课程（编号 0-3），课程之间的先修关系为：学习课程 1 前必须先学课程 0，学习课程 2 前必须先学课程 0，学习课程 3 前必须先学课程 1 和课程 2。
解题步骤：
- 建图：根据先修关系建立有向图：0→1, 0→2, 1→3, 2→3
- 计算入度：顶点 0 入度 0，顶点 1 入度 1，顶点 2 入度 1，顶点 3 入度 2
- 执行 Kahn 算法：入度为 0 的顶点 0 入队 → 处理后顶点 1、2 入度变为 0 → 依次处理 → 最终取出全部 4 个顶点
- 判断结果：排序结果包含 4 个顶点 = 总顶点数，说明课程安排可行
如果存在环（例如增加一条边 3→0），则算法执行过程中某些顶点的入度始终不会变为 0，最终排序结果的顶点数 < 总顶点数，说明课程安排存在循环依赖，不可行。
✨ 常见错误
- 忘记初始化入度数组：入度数组必须在遍历所有边之后才能使用，不能边建图边做拓扑排序
- 没有判断是否有环：拓扑排序结束后必须检查排序结果的顶点数是否等于总顶点数，否则无法检测出图中存在的环
- 混淆入度和出度：拓扑排序关注的是入度（指向该顶点的边数），不是出度
- 图的表示方式错误：边 u→v 表示 u 必须在 v 之前，建图时应从 u 指向 v，不要搞反方向
- 对有环图强行排序：如果题目没有保证图是 DAG，必须加上环检测逻辑
✨ 基于 DFS 的方法
基于 DFS 的拓扑排序利用递归堆栈来实现反向的顶点线性排序。
算法步骤：
- 对每一个未访问的节点执行 DFS。
- 在 DFS 访问过程中，一旦从一个节点的所有可达节点递归返回，就将该节点放入栈中。
- 最后的栈即为拓扑排序的结果，只需将其元素依次弹出。
下面的代码演示了基于 DFS 的拓扑排序实现方式：
1#include <iostream>
2#include <vector>
3#include <list>
4#include <stack>
5using namespace std;
6
7// 函数用于进行DFS，以探索图中的顶点
8void dfs(int v, vector<list<int>>& graph, vector<bool>& visited, stack<int>& stack) {
9 visited[v] = true; // 标记当前节点为已访问
10
11 // 遍历当前节点的所有邻接节点
12 for (int neighbor : graph[v]) {
13 if (!visited[neighbor]) { // 如果邻接节点未访问
14 dfs(neighbor, graph, visited, stack); // 递归访问它
15 }
16 }
17
18 // 所有从v出发可达的顶点都已被探访后，将v推入栈中
19 stack.push(v);
20}
21
22// 函数用于执行基于DFS的拓扑排序
23void topologicalSortDFS(vector<list<int>>& graph, int numVertices) {
24 stack<int> stack; // 用于存储拓扑排序的顶点
25 vector<bool> visited(numVertices, false); // 访问标记数组
26
27 // 对每个未访问的顶点调用DFS
28 for (int i = 0; i < numVertices; i++) {
29 if (!visited[i]) {
30 dfs(i, graph, visited, stack);
31 }
32 }
33
34 // 打印拓扑排序的结果
35 cout << "Topological Order: ";
36 while (!stack.empty()) {
37 cout << stack.top() << " ";
38 stack.pop();
39 }
40 cout << endl;
41}
42
43int main() {
44 // 顶点数
45 int numVertices = 6;
46 // 图的邻接表表示
47 vector<list<int>> graph(numVertices);
48 // 添加边，构造图
49 graph[5].push_back(2);
50 graph[5].push_back(0);
51 graph[4].push_back(0);
52 graph[4].push_back(1);
53 graph[2].push_back(3);
54 graph[3].push_back(1);
55
56 // 调用基于DFS的拓扑排序函数
57 topologicalSortDFS(graph, numVertices);
58
59 return 0;
60}三、课后练习
编程练习
- 家族树: L3373