拓扑排序：处理依赖关系的有序排列算法
拓扑排序（Topological Sort）是针对有向无环图（DAG） 的一种排序算法，其核心是根据节点间的依赖关系，生成一个满足所有前置条件的线性序列。例如在任务调度中，若任务 A 依赖于任务 B，则 A 必须在 B 之后执行，拓扑排序就是生成这样的合法执行顺序。
拓扑排序的核心概念
适用场景
拓扑排序仅适用于有向无环图（DAG），因为若图中存在环（如 A 依赖 B，B 依赖 C，C 依赖 A），则无法确定执行顺序，不存在拓扑排序。
核心目标
对于图中任意一条有向边<u, v>（u 指向 v），在拓扑排序结果中，u 必须排在 v 之前。
- 例：课程安排中，“数据结构” 是 “算法” 的前置课程，则 “数据结构” 必须排在 “算法” 之前。
拓扑排序的实现算法
拓扑排序的经典实现基于广度优先搜索（BFS），核心思路是反复寻找并移除入度为 0 的节点（无前置依赖的节点），具体步骤如下：
- 计算入度：统计每个节点的入度（指向该节点的边数）。
- 初始化队列：将所有入度为 0 的节点加入队列（这些节点可直接执行）。
- 处理队列：
- 出队一个节点
u，加入拓扑排序结果。
- 遍历
u的所有邻接节点v，将v的入度减 1（移除u对v的依赖）。
- 若
v的入度变为 0，将其入队。
- 检查结果：若拓扑排序结果包含所有节点，则成功；否则图中存在环，排序失败。
代码实现（Java）
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
72
73
74
75
76
77
78
79
80
81
82
83
84
| import java.util.*;
public class TopologicalSort {
private Map<String, List<String>> adjList;
private Map<String, Integer> inDegree;
public TopologicalSort() {
adjList = new HashMap<>();
inDegree = new HashMap<>();
}
public void addEdge(String u, String v) {
adjList.putIfAbsent(u, new ArrayList<>());
adjList.putIfAbsent(v, new ArrayList<>());
inDegree.putIfAbsent(u, 0);
inDegree.putIfAbsent(v, 0);
adjList.get(u).add(v);
inDegree.put(v, inDegree.get(v) + 1);
}
public List<String> sort() {
List<String> result = new ArrayList<>();
Queue<String> queue = new LinkedList<>();
for (String node : inDegree.keySet()) {
if (inDegree.get(node) == 0) {
queue.add(node);
}
}
while (!queue.isEmpty()) {
String u = queue.poll();
result.add(u);
for (String v : adjList.get(u)) {
inDegree.put(v, inDegree.get(v) - 1);
if (inDegree.get(v) == 0) {
queue.add(v);
}
}
}
if (result.size() != inDegree.size()) {
throw new IllegalArgumentException("图中存在环，无法拓扑排序");
}
return result;
}
public static void main(String[] args) {
TopologicalSort graph = new TopologicalSort();
graph.addEdge("起床", "锻炼");
graph.addEdge("起床", "刷牙");
graph.addEdge("起床", "打包午餐");
graph.addEdge("锻炼", "洗澡");
graph.addEdge("洗澡", "穿衣服");
graph.addEdge("刷牙", "吃早餐");
List<String> order = graph.sort();
System.out.println("拓扑排序结果（任务执行顺序）：");
for (String task : order) {
System.out.println(task);
}
}
}
|
拓扑排序的应用场景
- 任务调度
如项目管理中，任务之间存在依赖关系（如 “设计” 完成后才能 “开发”），拓扑排序可生成合法的任务执行顺序。
- 课程安排
大学课程中，先修课必须在后续课程前完成（如 “高等数学”→“线性代数”），拓扑排序可确定选课顺序。
- 编译依赖
程序编译时，模块 A 依赖模块 B，则 B 必须先编译，拓扑排序可确定编译顺序（如 Makefile 的依赖处理）。
- 代码依赖分析
分析代码中函数 / 类的调用关系，拓扑排序可检测循环依赖（如 A 调用 B，B 调用 A）。
总结
拓扑排序是处理依赖关系的核心算法，通过反复移除入度为 0 的节点，生成满足所有前置条件的线性序列。它仅适用于有向无环图，在任务调度、课程安排等场景中不可或缺
v1.3.10