拓扑排序：依赖解析的顺序与环

依赖解析最容易被低估的地方，不是写出 \(O(|V|+|E|)\) 的排序，而是三件工程问题：同一张图有很多合法顺序时怎样保持确定性；图里有环时怎样报告一条用户能修的具体环；依赖图增量变化时怎样不把整个世界重排一遍。拓扑排序只能解决“已知依赖图上的先后顺序”，不能替代包版本求解、冲突处理和条件依赖选择。

本文把有向边统一写成“前置任务 \(u\) 完成后，后继任务 \(v\) 才能开始”，即 \(u \to v\)。完整实验程序在同目录 reproduce/topo_experiments.py，它生成本文的逐步表、kahn-process.svg 和实验 CSV；生产实现只引用钉住版本的源码：CPython 3.12.0、Ninja v1.12.1、Go 1.23.4。

一、DAG、偏序与线性扩展

给定有向图 \(G=(V,E)\)。一个排列 \(\pi=(v_1,v_2,\ldots,v_n)\) 是拓扑序（topological order），当且仅当对每条边 \((u,v)\in E\)，\(u\) 在 \(\pi\) 中的位置小于 \(v\) 的位置：

\[ \operatorname{pos}_\pi(u) < \operatorname{pos}_\pi(v). \]

拓扑序存在当且仅当 \(G\) 是有向无环图（Directed Acyclic Graph，DAG）。必要性很直接：若有环 \(v_0\to v_1\to \cdots \to v_k=v_0\)，位置必须严格递增又回到起点，矛盾。充分性来自 DAG 至少有一个入度为 \(0\) 的顶点：若每个顶点都有入边，从任意顶点沿入边反向追溯，有限图中必定重复顶点并形成环。反复删去入度为 \(0\) 的顶点就得到一个拓扑序。

DAG 也定义了一个偏序：若存在从 \(u\) 到 \(v\) 的路径，就写作 \(u\prec v\)。拓扑排序就是这个偏序的线性扩展（linear extension）。这解释了两条常被混在一起的复杂度结论：

因此，“给一个可用顺序”容易，“有多少种顺序”很难；工程系统通常需要的是前者加上确定性和诊断能力。

二、Kahn 算法：剥离入度为零的顶点

Kahn 在 1962 年的 CACM 论文 Topological sorting of large networks 中给出一种面向大型 PERT 网络的拓扑排序方法。今天常用的队列版可以写成下面几步：

compute indeg[v] for every v
ready = all vertices with indeg[v] == 0
while ready is not empty:
    u = pop one vertex from ready
    output u
    for each edge u -> v:
        indeg[v] -= 1
        if indeg[v] == 0:
            push v into ready
if output does not contain all vertices:
    report a cycle

每个顶点最多入队、出队一次，每条边只在其起点被输出时访问一次，所以时间是 \(O(|V|+|E|)\)，额外空间是 \(O(|V|)\)。下面的例子由 reproduce/topo_experiments.py 生成，边表示依赖释放方向：

同一程序输出的逐步表如下。ready_before 是本步弹出前的就绪队列，released 是本步入度降到 \(0\) 的后继。

这张图有 \(7\) 个顶点、\(9\) 条边；程序统计 Kahn 访问边数为 \(9\)，队列操作为 \(14\)（每个顶点入队、出队各一次）。这个计数比运行时间更稳定，因为当前机器上有其他任务并行运行。

Kahn 算法的一个重要性质是“就绪集合”可以一次返回多个顶点。CPython 3.12.0 的 graphlib.TopologicalSorter 正是这样暴露并行语义：prepare() 固定图并初始化 _ready_nodes；get_ready() 返回当前所有就绪节点的 tuple，并把它们标记为 _NODE_OUT；调用者完成任务后再用 done(*nodes) 递减后继的 npredecessors，新就绪节点进入下一轮 _ready_nodes。即使 prepare() 发现环并抛出 CycleError，源码仍然允许调用者继续 get_ready()，取出所有不被环阻塞的节点。

三、DFS 版：后序逆序与一条具体环

DFS 版依赖三色标记：白色表示未访问，灰色表示在当前递归栈上，黑色表示已完成。访问 \(u\) 时递归访问每个后继 \(v\)；当 \(u\) 的所有后继都完成后，把 \(u\) 放进结果。最后反转完成序就是拓扑序。对任意边 \(u\to v\)，若先进入 \(u\)，则 \(v\) 会先于 \(u\) 完成；若先进入 \(v\)，在 DAG 中 \(v\) 不可能仍是 \(u\) 的灰色祖先，所以 \(v\) 也先完成。反转后 \(u\) 排在 \(v\) 前。

Tarjan 1972 年的 Depth-First Search and Linear Graph Algorithms 把 DFS 作为线性时间图算法的基础工具；用户常提到的 Tarjan 1976 年 Acta Informatica 6 论文确实存在，但题目是 Edge-disjoint spanning trees and depth-first search，不是“DFS 拓扑排序版”的原始出处。本文只把 1976 年论文列入 DFS 谱系，不把它说成拓扑排序算法来源。

DFS 最大的诊断优势是能直接取出一条环：遇到边 \(u\to v\) 且 \(v\) 是灰色时，递归栈中从 \(v\) 到栈顶 \(u\) 的片段，加上回边 \(u\to v\)，就是一条具体环。复现程序在图

\[ a\to b, \quad b\to c, \quad c\to a, \quad c\to d, \quad d\to e \]

上访问前 \(3\) 条边后报告：

a -> b -> c -> a

Kahn 算法也能判环，但它结束时留下的是“仍未输出的顶点集合”。这个集合可能包含环上的顶点，也可能包含依赖于环的下游顶点；要报告一条环，仍需在剩余导出子图上跑一次 DFS，或先找强连通分量（Strongly Connected Components，SCC）。对用户来说，“存在环”通常不够；构建工具、包管理器和工作流系统至少要打印一条闭合路径。

四、确定性：队列、堆与字典序最小拓扑序

Kahn 算法中的 ready 不是数学集合那么简单。若用 FIFO 队列，输出依赖于顶点扫描顺序和邻接表顺序；若这些顺序来自哈希表，结果可能跨进程、跨机器变化。可复现构建通常需要稳定规则。

要求所有合法拓扑序中字典序最小的一个时，把 ready 换成最小堆即可：每次从当前所有入度为 \(0\) 的顶点中取名称或编号最小者。正确性来自贪心交换：设第一个不同位置上，算法取了当前可选的最小顶点 \(x\)，另一合法序取了 \(y>x\)。由于 \(x\) 当前没有未输出前驱，把 \(x\) 提前到这个位置不会破坏任何依赖，且字典序更小。

代价是每个顶点一次入堆、一次出堆，复杂度变为

\[ O(|E| + |V|\log |V|). \]

最大字典序同理：在原图上把最小堆换成最大堆，每步取当前最大的就绪点即可；交换论证与最小字典序完全对称。容易混淆的是另一个问题：“让编号 1 尽量靠前，其次让 2 尽量靠前……”的顺序约束不是最小字典序，它的标准做法才是在反向图上用最大堆生成序列再整体反转。例如只有边 \(3\to 1\) 时，最小字典序是 \([2,3,1]\)，而“1 尽量靠前”的答案是 \([3,1,2]\)。

本文实验的随机 DAG 规模为 \(|V|=200\)、边概率 \(0.035\)，种子为 13,17,19,23,29。所有算法都逐条验证每条边满足 \(\operatorname{pos}(u)<\operatorname{pos}(v)\)。

表里“堆操作”没有展开比较次数，只统计入堆与出堆次数；真正的额外成本来自每次堆操作的 \(\log |V|\) 比较。实验口径有意避开 wall-clock，只比较访问边数和队列/堆操作次数。

五、并行调度与关键路径

拓扑序是一个线性顺序，但调度器真正需要的是“现在能跑哪些任务”。Kahn 的 ready 集合天然提供这个接口：所有前驱已经完成的任务都可以交给 worker；某个任务完成后，递减后继的未完成前驱计数，计数归零者进入就绪集合。

这也是 CPython TopologicalSorter.prepare/get_ready/done 的分工：get_ready() 一次返回当前批次，调用者可以并行处理；done() 是释放后继的同步点。这样的接口比直接返回一个列表更适合构建系统和任务图执行器，因为它不强迫所有任务严格按某个线性拓扑序串行运行。

若每个顶点 \(v\) 有持续时间 \(d(v)\)，DAG 的最短完工时间下界是关键路径长度：

\[ \operatorname{dist}(v)=d(v)+\max_{u\to v}\operatorname{dist}(u), \]

源点的最大前驱项取 \(0\)。按任意拓扑序做一次动态规划即可求出所有 \(\operatorname{dist}(v)\)。这解释了为什么“开更多线程”不能无限加速构建：当最长依赖链很长时，额外 worker 只能填充旁支，不能缩短关键路径。

Ninja v1.12.1 的 src/build.cc 可以直接看到这种“就绪即执行”的 Kahn 变体。Plan::AddSubTarget() 递归把目标的输入边加入计划；ScheduleInitialEdges() 扫描 want_，把 edge->AllInputsReady() 的边放入 ready_；Plan::FindWork() 从 ready_ 弹出一条边；Plan::EdgeFinished() 标记输出 ready，再通过 NodeFinished() 和 EdgeMaybeReady() 释放下游边。Builder::Build() 的主循环先按 CommandRunner::CanRunMore() 启动尽可能多的 ready 边，再等待完成事件。这不是“先算完整拓扑序再逐层执行”，而是在线维护就绪集合。

六、依赖解析不等于版本求解

拓扑排序要求图已经确定；包管理器还要先决定图里有哪些版本、可选依赖选哪条、冲突约束是否可满足。把这一步说成拓扑排序会掩盖真正困难的地方。

Go 1.23.4 的 cmd/go/internal/load/pkg.go 体现了两个层次：

• 源码 import 图加载由 loadImport() 递归完成；reusePackage() 用 p.Internal.Imports == nil 判断某包还在自己的加载过程中，设置 PackageError{Err: "import cycle not allowed", IsImportCycle: true}。这是包 import 图上的环诊断。
• Go module 的版本选择遵循 Go module reference 中的 Minimal Version Selection（MVS）。MVS 选择模块版本后，编译包的先后仍需按 import DAG 处理；但版本选择本身不是拓扑排序。

Debian、RPM、Cargo 这类系统还会遇到更丰富的版本区间、冲突、虚拟包和特性选择。Mancinelli 等人在 ASE 2006 的 EDOS 工作中把大型发行版依赖管理建模为约束问题，并讨论了 SAT 求解器在其中的角色。工程上应把流程拆成两步：先解约束得到一个具体依赖图，再在这个图上拓扑排序或报告环。

七、增量拓扑序：插入一条边时少重排

IDE、构建守护进程和工作流平台常常面对动态图：用户改一个文件，依赖边增删一两条。如果每次都重新跑完整 Kahn，复杂度虽然仍是线性的，但在百万级节点图上会带来可见延迟。

维护一个当前拓扑序 \(\pi\)。插入新边 \(u\to v\) 时分三种情况：

1. 若 \(\operatorname{pos}_\pi(u)<\operatorname{pos}_\pi(v)\)，当前顺序仍合法，不需要重排。
2. 若 \(v\) 能到达 \(u\)，新边形成环，报告路径 \(v\leadsto u\to v\)。
3. 否则只需重排区间 \([\operatorname{pos}_\pi(v),\operatorname{pos}_\pi(u)]\) 中受影响的顶点。

Pearce 与 Kelly 2006 年的 JEA 论文给出一种工程上简单的动态拓扑排序算法。本文复现程序实现的是同一思想的简化版：在上述区间内，从 \(v\) 向前搜到必须放到后面的集合，从 \(u\) 沿反向边搜到必须放到前面的集合，只重排两类受影响顶点，并在每次插边后验证所有边方向。

随机实验从空图开始，按一个隐藏真拓扑序生成 \(240\) 条合法插边，规模为 \(|V|=200\)。表中“零重排”表示插边已满足当前顺序；“最大重排”是该分桶中一次插边触及的节点数。

这组数据不能代表所有负载，只说明一个常见工程现象：当新增边大多与当前顺序一致时，增量算法经常不动或只动很小窗口。最坏情况仍可能很差，所以研究谱系没有停在 1996/2006：Marchetti-Spaccamela、Nanni、Rohnert 1996 年研究边插入下的拓扑序维护；Bender、Fineman、Gilbert、Tarjan 2015 年在 TALG 给出增量环检测与相关问题的新算法，分别针对稀疏和稠密图改进总更新时间。开放问题不是“能否维护”，而是在简单实现、局部性、最坏界和真实图分布之间怎样取舍。

八、可复现实验

复现命令：

cd /home/ltl/repos/2bzltl
taskset -c 13 python3 post/algorithms/48-topo-sort/reproduce/topo_experiments.py

环境：Intel Core i9-12900K，24 逻辑 CPU；Linux 6.6.87.2-microsoft-standard-WSL2；Python 3.14.5。本文没有使用计时数据，只使用访问边数、队列/堆操作次数和重排节点数。程序输出：

• kahn_steps.csv：第二节逐步表的来源；
• random_dag_metrics.csv：第四节随机 DAG 指标；
• incremental_insertions.csv 与 incremental_summary.csv：第七节增量插边指标；
• kahn-process.svg：第二节图，脚本按示例图坐标与真实执行步骤生成。

程序内置三类断言：Kahn、堆版 Kahn、DFS 的输出都必须满足每条边的方向；环示例必须报告闭合路径；增量插边每一步后都重新检查所有已插入边。若断言失败，脚本直接退出，不写入误导性结果。

九、工程陷阱与选型

选型可以按目标拆开：

• 只要一个顺序：Kahn 或 DFS 都可以；需要避免递归深度时选 Kahn。
• 要并行执行：维护 Kahn ready 集合，像 TopologicalSorter.get_ready()/done() 或 Ninja 的 Plan 那样边完成边释放。
• 要确定性：用堆或显式排序的 ready 集合，并固定邻接表顺序。
• 要一条可读的环：DFS 三色栈最直接；Kahn 判环后再在剩余子图 DFS。
• 图频繁变化：从 Pearce–Kelly 这类增量算法起步，记录每次重排窗口大小，再决定是否需要更复杂的理论算法。

拓扑排序的工程边界可以浓缩成一句话：它负责把已知 DAG 线性化；DAG 的正确性、约束求解、环诊断、确定性和增量维护，才是依赖解析器真正难的部分。

十、参考资料

规范与文档

• Python 3.12 Standard Library, graphlib 文档与 CPython 3.12.0 Lib/graphlib.py。
• Go Modules Reference, go.dev/ref/mod，Minimal Version Selection 与 module 版本规则。

源码

• CPython 3.12.0，Lib/graphlib.py：TopologicalSorter.add()、prepare()、get_ready()、done()、_find_cycle()。
• Ninja v1.12.1，src/build.cc：Plan::AddSubTarget()、ScheduleInitialEdges()、FindWork()、EdgeFinished()、Builder::Build()。
• Go 1.23.4，cmd/go/internal/load/pkg.go：loadImport()、reusePackage()、PackageError.IsImportCycle。

核心论文

• A. B. Kahn, “Topological sorting of large networks”, Communications of the ACM 5(11), 1962. DOI: 10.1145/368996.369025。
• Robert Tarjan, “Depth-First Search and Linear Graph Algorithms”, SIAM Journal on Computing 1(2), 1972. DOI: 10.1137/0201010。
• Graham Brightwell, Peter Winkler, “Counting linear extensions is #P-complete”, STOC 1991；期刊版 Order 8(3), 1991. DOI: 10.1145/103418.103441、10.1007/BF00383444。

增量与依赖求解

• Alberto Marchetti-Spaccamela, Umberto Nanni, Hans Rohnert, “Maintaining a topological order under edge insertions”, Information Processing Letters 59(1), 1996. DOI: 10.1016/0020-0190(96)00075-0。
• David J. Pearce, Paul H. J. Kelly, “A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs”, Journal of Experimental Algorithmics 11, Article 1.7, 2006/2007. DOI: 10.1145/1187436.1210590。
• Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Robert E. Tarjan, “A New Approach to Incremental Cycle Detection and Related Problems”, ACM Transactions on Algorithms 12(2), Article 14, 2015. DOI: 10.1145/2756553。
• Fabio Mancinelli, Jaap Boender, Roberto Di Cosmo, Jérôme Vouillon, Berke Durak, Xavier Leroy, Ralf Treinen, “Managing the Complexity of Large Free and Open Source Package-Based Software Distributions”, ASE 2006. DOI: 10.1109/ASE.2006.49。

实验

• reproduce/topo_experiments.py：本文 SVG、逐步表、随机 DAG 对拍和增量插边指标的生成程序。

系列导航： - 上一篇：网络流与二分匹配 - 下一篇：PageRank 与随机游走：从链接投票到工程实现

相关阅读： - Tarjan 算法族：SCC、割点、桥的统一框架 - CPU 调度：CFS 的虚拟运行时间与 EEVDF 的虚拟截止期 - 竞争分析与在线算法