数据结构与算法 / 系统课时

Kahn 算法怎么找拓扑序

Kahn 算法怎么找拓扑序

当任务之间存在“先完成 A,才能执行 B”的依赖时,拓扑排序要把有向无环图中的节点排成合法先后顺序。Kahn 算法从入度为 0 的节点开始,每处理一个节点就解除它对后继的约束,因此还能顺便判断图中是否存在环。

学习目标

  • 能用入度数组和队列构造一个合法拓扑序
  • 能根据最终处理节点数判断有向图是否存在环
  • 能分析 Kahn 算法的时间与空间复杂度

入度为什么能表示“当前可执行”

对边 u -> v 来说,v 的入度表示仍有多少前置节点尚未被移除。入度为 0 的节点当前没有未满足依赖,可以立即加入处理队列。

取出一个节点 u 后,相当于把它和所有出边从剩余图中删除,因此每个后继 v 的入度减 1。某个后继首次降到 0 时,它的全部前置条件都已完成,于是进入队列。

Kahn 算法按入度逐步解除依赖

用队列构造拓扑序

下面的 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,剩余节点中必然存在环。这个判断不需要额外再跑一次环检测算法。

复杂度与使用边界

构建邻接表和入度需要扫描全部边,主循环中每个节点最多入队一次、每条边最多处理一次,因此时间复杂度是 O(V+E)O(V+E),邻接表、入度数组和队列占用 O(V+E)O(V+E) 空间。

Kahn 算法适合课程依赖、构建任务、工作流调度等“先满足前置条件再执行”的场景。如果还需要字典序最小的拓扑序,可以把普通队列换成最小堆;核心不变,仍然只选择当前入度为 0 的节点。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Kahn 算法怎么找拓扑序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通