拓扑排序计算器

伪代码

两种标准写法，都是线性的。Kahn 从没有前置依赖的结点开始正向推进；DFS 版本则借助完成时间反向推导。

// Kahn：反复移除一个没有入边的结点
计算每个结点的 入度[v]
队列 = 所有入度为 0 的结点
顺序 = []

当队列非空时:
    u = 队列.取出()
    顺序.追加(u)
    对每条边 (u, v):
        入度[v] -= 1
        若 入度[v] == 0: 队列.放入(v)

若 顺序.长度 < V: 图中存在环

// DFS 变体：完成顺序的逆序
执行 DFS；每个结点完成时压入栈中
把栈弹空所得到的序列就是一个合法的拓扑序

Kahn 有一个值得了解的实用优势：由于它是通过统计成功输出了多少结点来判断有没有环的，剩下未输出的那些结点恰好就是位于环中或位于环下游的结点。当你需要报告究竟是哪些依赖构成了循环时，这比一个布尔值有用得多。

分步示例演算

在一个小型构建依赖图上运行 Kahn，其中边 X 到 Y 表示 X 必须先于 Y 构建。

示例图: 有向边 A 到 C、B 到 C、C 到 D 和 B 到 D。

1. 计算入度. A 为 0，B 为 0，C 为 2（来自 A 与 B），D 为 2（来自 C 与 B）。队列以 A 和 B 开始。
2. 输出 A. 顺序为 [A]。把 C 的入度减为 1。还不是零，因此 C 尚未入队。
3. 输出 B. 顺序为 [A, B]。把 C 的入度减为 0，于是 C 入队。把 D 的入度减为 1。
4. 输出 C. 顺序为 [A, B, C]。把 D 的入度减为 0，于是 D 入队。
5. 输出 D. 顺序为 [A, B, C, D]。队列已空，且四个结点全部输出，因此不存在环。

一个合法的顺序是 A、B、C、D。请注意 B、A、C、D 同样合法：A 与 B 都没有前置依赖，它们之间的相对顺序不受约束。除非整个图是一条链，否则拓扑序并不唯一，因此测试应当验证输出中每条边都指向前方，而不是与某个预期序列逐一比对。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

计算全部入度需要扫一遍所有边，为 O(E)。每个结点恰好入队一次、出队一次，为 O(V)。每条边也恰好被检查一次，即在其起点被输出、终点入度递减的时候，又是 O(E)。空间用于保存入度数组、队列和输出列表，都是 O(V)。DFS 变体的界限相同，只是用递归栈代替了队列。两者都无法再改进，因为任何正确的算法都必须读完所有边才能知道全部约束。

何时使用拓扑排序，何时不宜

Kahn 与 DFS 给出的顺序同样合法。选哪个取决于你在排序之外还需要什么。

常见陷阱

• 在含环的图上运行却毫无察觉. 含环的图根本不存在拓扑序。除非你把输出长度与 V 比对，Kahn 会悄悄给出一个不完整的部分顺序。这项比对就是环检测，省掉它会得到一个看似合理却不完整的构建顺序。
• 期待答案唯一. 任何两个彼此之间没有路径的结点都可以按任意先后出现。拿输出与硬编码的序列比对，会让完全正确的实现在测试中失败；应当改为验证输出中每条边都指向前方。
• 搞反边的方向. 如果边 X 到 Y 的含义是「X 依赖 Y」，那么拓扑序恰好与你想要的相反。请在构建图的那一处把约定一次性理顺，而不是把输出反转过来碰运气。
• 把它用在无向图上. 拓扑序只对有向无环图有定义。一条无向边就是一个长度为二的环，因此任何含有边的无向图都不存在拓扑序。
• DFS 变体递归过深. 一条包含数万个结点的依赖链会让调用栈溢出。Kahn 是迭代的，不存在这个限制，这也是构建工具往往偏爱它的原因之一。

常见问题

拓扑排序有什么用？

它把有向无环图的结点排成一列，使每条边都指向前方，从而回答「在给定依赖关系下，这些任务能按什么顺序执行」这个问题。它用于调度 Make、Gradle 之类的构建系统，解析软件包的安装顺序，安排有先修要求的课程，为电子表格的单元格求值排序，以及在编译器中安排指令的执行顺序。

Kahn 算法与 DFS 做法有什么区别？

Kahn 借助队列反复移除入度为零的结点，从没有前置依赖的部分向前推进。DFS 做法则执行一次深度优先搜索，并按完成时间的逆序输出结点。两者都是 O(V + E)，也都给出合法的顺序。Kahn 是迭代的，还能报告哪些结点位于环中；DFS 更简短，但是递归的。

一个图可能有多个拓扑序吗？

几乎总是如此。任何两个彼此之间没有有向路径的结点都可以按任意先后出现，因此一个结点数为 V、边很少的图可能拥有极其大量的合法顺序。只有当图中存在哈密顿路径时顺序才唯一，对 DAG 而言这意味着一条贯穿所有结点的链。

如何在拓扑排序过程中检测环？

用 Kahn 时统计输出的结点数：若少于 V，剩下的那些就位于环中或环的下游，因为它们的入度从未降到零。用 DFS 变体时，一条指向仍在递归栈中的结点的回边即可证明存在环。

拓扑排序的时间复杂度是多少？

无论 Kahn 还是 DFS 变体，都是 O(V + E) 时间和 O(V) 空间。每个结点处理一次，每条边检查一次。这是最优的，因为任何算法都至少要把所有依赖边读一遍。