数据结构与算法 / 系统课时
Kahn 算法怎么找拓扑序
Kahn 算法怎么找拓扑序
当任务之间存在“先完成 A,才能执行 B”的依赖时,拓扑排序要把有向无环图中的节点排成合法先后顺序。Kahn 算法从入度为 0 的节点开始,每处理一个节点就解除它对后继的约束,因此还能顺便判断图中是否存在环。
学习目标
- 能用入度数组和队列构造一个合法拓扑序
- 能根据最终处理节点数判断有向图是否存在环
- 能分析 Kahn 算法的时间与空间复杂度
入度为什么能表示“当前可执行”
对边 u -> v 来说,v 的入度表示仍有多少前置节点尚未被移除。入度为 0 的节点当前没有未满足依赖,可以立即加入处理队列。
取出一个节点 u 后,相当于把它和所有出边从剩余图中删除,因此每个后继 v 的入度减 1。某个后继首次降到 0 时,它的全部前置条件都已完成,于是进入队列。

用队列构造拓扑序
下面的 Python 示例先统计入度,再把所有初始入度为 0 的节点放入队列。若最终结果长度小于节点数,就返回 None 表示无法完成拓扑排序。
python
from collections import deque
def topo_sort(n, edges):
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
# 初始可执行节点:没有任何未满足前置依赖
queue = deque(i for i in range(n) if indegree[i] == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order if len(order) == n else None
dag_edges = [(0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
cycle_edges = [(0, 1), (1, 2), (2, 1)]
print("DAG:", topo_sort(6, dag_edges))
print("有环:", topo_sort(3, cycle_edges))预期输出
text
DAG: [0, 1, 2, 3, 4, 5]
有环: None同一张 DAG 可能有多个合法拓扑序。只要每条边 u -> v 中 u 都出现在 v 前面,结果就是正确的;队列中同时出现多个入度为 0 的节点时,选择顺序会影响最终序列。
为什么能检测有向环
如果图中存在一个有向环,环上的每个节点都至少有一条来自环内的入边。即使所有环外节点已经处理完,这些节点的入度仍不会降到 0,因此永远进不了队列。
所以判断条件非常直接:若最终得到的拓扑序包含全部 n 个节点,图是 DAG;若处理数小于 n,剩余节点中必然存在环。这个判断不需要额外再跑一次环检测算法。
复杂度与使用边界
构建邻接表和入度需要扫描全部边,主循环中每个节点最多入队一次、每条边最多处理一次,因此时间复杂度是 ,邻接表、入度数组和队列占用 空间。
Kahn 算法适合课程依赖、构建任务、工作流调度等“先满足前置条件再执行”的场景。如果还需要字典序最小的拓扑序,可以把普通队列换成最小堆;核心不变,仍然只选择当前入度为 0 的节点。
按自己的节奏,确认真正理解。