拓扑排序 | Codeboy's Blog

形式陈述

有限有向图 $D=(V,A)$ 的拓扑序是顶点排列

v_1,v_2,\ldots,v_n

使每条弧 $(v_i,v_j)\in A$ 都满足 $i<j$ 。这样的排列存在，当且仅当 $D$ 是有向无环图（DAG）。必要性很直接：若有向圈上的每条弧都从前指向后，沿圈一周会推出某个顶点严格早于自身。充分性可由“每个非空有限 DAG 都有入度为零的顶点”归纳得到；否则从任一点不断沿入边逆行，有限性会迫使顶点重复并形成有向圈。

Kahn 算法维护当前入度为零顶点的集合。取出一个顶点 $u$ 输出，并删除它的所有出弧；某个后继的剩余入度降至零时，将其放入队列或其他候选容器。循环不变量是：已输出前缀内部及其指向未输出区的每条弧都与该前缀次序相容，而候选顶点在剩余图中没有前驱。若共输出 $n$ 个顶点，所得排列合法；若候选集为空而仍有顶点，剩余有限图的每个顶点都有入边，故含有向圈。

另一种实现用深度优先搜索。搜索时若遇到指向灰色祖先的回边，就报告有向圈；若没有回边，按完成时间递减排列顶点。对任意弧 $u\to v$ ，无回边条件保证 $f[u]>f[v]$ ，所以 $u$ 出现在 $v$ 之前。

在出邻接表、显式入度数组与单位成本 RAM 下，Kahn 版本初始化和扫描各用 $\Theta(|V|+|A|)$ 时间、 $O(|V|)$ 辅助空间；DFS 版本具有相同渐近界。若用最小堆而非 FIFO 容器选择候选，输出可固定为字典序最小的拓扑序，时间变为 $O((|V|+|A|)\log |V|)$ 。

直觉

每条弧只声明一项局部先后约束，拓扑排序把这些约束扩展为一条可顺序执行的总次序。Kahn 算法从“现在已经没有前置条件”的一端构造前缀；DFS 则等所有后继完成后才关闭顶点，再把关闭次序反转。两种视角分别剥离源点与汇向结构，依靠的都是不能沿依赖链回到自身。

拓扑序把不可比较的顶点人为排出先后。例如两个独立任务可以交换位置，输出中的先后并不新增依赖。若应用关心并行度，应回到 DAG 的偏序与最长依赖链；某一次线性扩张不能代表唯一调度。

例子与边界

依赖弧为

A\to C,\qquad B\to C,\qquad C\to D.

初始零入度集合是 $\{A,B\}$ 。先取 $A$ 时 $C$ 的剩余入度由 $2$ 降到 $1$ ，再取 $B$ 才降为 $0$ ，随后输出 $C,D$ 。因此 $A,B,C,D$ 与 $B,A,C,D$ 都合法；如果全图没有弧，任意排列都合法，共有 $n!$ 种。

加入 $D\to B$ 后，剩余顶点 $B,C,D$ 形成有向圈。Kahn 算法输出 $A$ 后便无候选，处理数小于 $|V|$ ；DFS 会在活动栈上遇到回边。只记录一个 visited 位无法区分“仍在当前递归路径”与“已经完成”，因而不足以可靠检测有向圈。

平行弧不改变合法排列，却会改变存储的入度计数；若保留两条 $u\to v$ 记录，初始化要加二，删除 $u$ 时也必须减二。也可以先合并重复弧，但不能只在其中一个阶段去重。若模型允许自环 $v\to v$ ，它本身就是有向圈，不存在拓扑序。

推论与应用

沿拓扑序扫描，处理 $v$ 时它的所有前驱都已完成，因此 DAG 上的最短路、最长路和路径计数都可做一次前向动态规划；边权即使为负也不妨碍 DAG 最短路，因为没有圈可让估计反复回流。构建系统、课程先修和数据流调度使用的是同一依赖不变量，但还需分别定义任务成本与资源约束。

含圈图不能先“随便删一条边”再排序，因为删边改变了依赖语义。若允许把互相依赖的顶点作为一个整体处理，可先求强连通分量并收缩；凝聚图一定是 DAG，随后只能得到分量之间的拓扑序，圈内顶点仍无合法线性次序。

工作—深度模型进一步用总工作与最长链刻画并行执行。拓扑序只提供一个合法串行化，不会把原本可并行的两个零入度任务变成真正的依赖。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§20.4。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，§3.6。

形式陈述 ​

反向链接

形式陈述