拓扑排序
01 / 一句话本质
把一张有向无环图线性化,使输出中每条边都从左指向右 — 每个节点都只有在所有指向它的节点都已经出列之后才能进入这个顺序。
题目DAG 的拓扑排序节点数4边数4
统计入度。没有入边的节点就是源点 — 可以最先处理。
步
0 / 13
队列
[—]
动作
初始化
结果
[—]
0 / 13
02 / 模式骨架
# Kahn 算法 — 从源点队列出发,把入度依次"抽干"in_degree ← 统计每个节点的入边数queue ← 所有 in_degree[node] == 0 的节点result ← []while queue 非空:u ← queue.pop_front()result.append(u)for v in adj[u]:in_degree[v] -= 1if in_degree[v] == 0: queue.append(v)if len(result) < n: # 检测到环return []return result
03 / 什么时候用这个模式
"先修 / 依赖"
课程安排、任务排序、构建系统、包管理器、公式表格。任何带有依赖图的场景都需要拓扑序。
"到底能不能找到某种顺序?"
同样的算法可以检测是否存在合法顺序。如果 Kahn 的队列提前空了, 剩下没处理的节点就构成一个环 — 答案是不能。LC 207 就是这个问题。
"DAG"
题面里直接出现有向无环图。看到 "DAG" 这三个字,拓扑排序就是脊梁 — DAG 上的最长路径、最短路径、路径计数,统统挂在它身上。
"BFS 看着对,但顺序很重要"
普通 BFS 会随意展开邻居,但题目要求必须遵守依赖关系时, 你其实是在依赖 DAG 上跑 Kahn 算法。
04 / 常见坑
i.
搞反边的方向。
输入里的
(a, b) 可能是 "a 是 b 的先修"(a → b), 也可能是 "a 依赖 b"(b → a)。题面要看仔细 — 两种情况算法都对, 但只有一种符合题目想要的顺序。LC 210 里 [a, b] 表示 "要修 a,必须先修 b",这与常见的边记法相反。ii.
把"无环"和"存在合法顺序"混为一谈。
对 DAG 而言这是同一个条件,但代码层面的失败方式不同。 要检测环,就在结尾比较
len(result) == n,而不是提前去找。 Kahn 算法天然会拒绝含环的输入。iii.
假设顺序唯一。
大多数 DAG 有许多合法的拓扑顺序。如果题目要求"字典序最小的顺序"(LC 269), 把队列换成最小堆即可 — Kahn 的其余部分保持不变。
05 / 去 LeetCode 上练习
家族中的四道题。前两道是教科书式的"判环 / 输出顺序"配对。 第三道把算法提升为一种推导(从单词顺序反推字母表);第四道引入并行执行带来的余量。