什么是拓扑排序？
拓扑排序（Topological Sort）是对有向无环图（DAG, Directed Acyclic Graph） 中的顶点进行排序的算法，使得所有有向边都从排在前面的顶点指向后面的顶点。
简单来说：如果任务 A 依赖任务 B，那么 B 必须排在 A 前面。拓扑排序就是找出这个先后顺序的算法。
注意：只有 DAG 才有拓扑排序，图中存在环则无法排序。
Kahn 算法（BFS 方法）
最常用的拓扑排序算法是 Kahn 算法，核心思想是：
- 计算每个顶点的入度（有多少边指向它）
- 将所有入度为 0 的顶点加入队列（这些是没有依赖的起始任务）
- 从队列取出一个顶点，将其加入排序结果
- 将该顶点指向的所有顶点的入度减 1
- 如果有顶点的入度变为 0，则加入队列
- 重复 3-5，直到队列为空
from collections import deque
def topological_sort(n, edges):
"""
n: 顶点数
edges: 边列表，每条边为 [from, to]，表示 to 依赖于 from
"""
# 构建邻接表和入度数组
adj = [[] for _ in range(n)]
indegree = [0] * n
for from_node, to_node in edges:
adj[from_node].append(to_node)
indegree[to_node] += 1
# 入度为0的顶点入队
queue = deque([i for i in range(n) if indegree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in adj[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
# 如果有环，队列会提前变空
if len(result) != n:
return "图中存在环，无法拓扑排序"
return result
# 示例：课程选修顺序
# 课程0 -> 课程1 -> 课程2
edges = [
[0, 1], # 课程1依赖于课程0
[1, 2] # 课程2依赖于课程1
]
print(topological_sort(3, edges))
# 输出: [0, 1, 2]
DFS 方法（深度优先遍历）
另一种拓扑排序方法是基于 DFS 的后序遍历反转：
def topological_sort_dfs(n, edges):
adj = [[] for _ in range(n)]
for from_node, to_node in edges:
adj[from_node].append(to_node)
visited = [0] * n # 0=未访问, 1=访问中, 2=已完成
result = []
def dfs(node):
if visited[node] == 1: # 遇到"访问中"的节点，说明有环
return False
if visited[node] == 2: # 已完成，直接返回
return True
visited[node] = 1 # 标记为访问中
for neighbor in adj[node]:
if not dfs(neighbor):
return False
visited[node] = 2 # 标记为已完成
result.append(node) # 后序加入结果
return True
for i in range(n):
if not dfs(i):
return "图中存在环"
result.reverse() # 反转后得到拓扑序
return result
# 测试
edges = [[0,1], [1,2]]
print(topological_sort_dfs(3, edges))
# 输出: [0, 1, 2]
复杂度分析
| 指标 | Kahn 算法 | DFS 方法 |
|---|---|---|
| 时间复杂度 | O(V + E) | O(V + E) |
| 空间复杂度 | O(V + E) | O(V + E) |
其中 V 是顶点数，E 是边数。
经典应用场景
- 课程选修顺序（Course Schedule）：大学课程有先修要求，计算选课顺序
- 项目构建顺序（Build System）：Makefile、Gradle 等构建工具分析依赖顺序
- 任务调度（Task Scheduling）：有依赖关系的任务并行调度
- 源代码依赖顺序：头文件的包含顺序
- 病毒检测（Family tree）：家族血统的拓扑排序
总结
拓扑排序是处理有依赖关系任务排序的利器。核心是识别”入度为0”的起始任务，然后逐步消除依赖。Kahn 算法直观易懂，DFS 方法更优雅。两者时间复杂度相同，都是 O(V+E)。