拓扑排序

你敲下 make 编译一个 C 项目，或者 npm install 装一堆依赖包：a.o 必须先于 b.o 编译，库 X 必须先于依赖它的库 Y 安装。构建工具要做的第一件事，就是把这张"谁依赖谁"的关系图，理成一条所有依赖都排在前面的执行顺序——这就是拓扑排序（Topological Sort）。

Excel 也在做同样的事：当你改动一个单元格，公式引擎要按"被引用的格子先算"的顺序重算整张表，否则就会用到尚未更新的旧值。

拓扑排序只对有向无环图（DAG，Directed Acyclic Graph）有意义——如果存在环（A 依赖 B，B 依赖 A），则没有合法顺序。这也是为什么 Excel 检测到循环引用会直接报错，make 遇到循环依赖会拒绝构建。

形式定义#

给定有向无环图 $G = (V, E)$，拓扑排序是节点的一个线性排列，使得对每条边 $(u, v) \in E$，$u$ 在排列中出现在 $v$ 之前。直白说：若 $u \to v$（$u$ 是 $v$ 的前驱），则在排列中 $u$ 必须排在 $v$ 前面。

不唯一性：拓扑排序通常不唯一。例如若 $A \to C$ 且 $B \to C$，则 $A, B, C$ 和 $B, A, C$ 都是合法的拓扑序。

Kahn 算法（BFS 版本）#

由 Arthur B. Kahn 在 1962 年提出。基于"入度为 0 的节点可以最先处理"的直觉。

入度（in-degree）：指向某节点的边的数量，代表"还有多少前驱未完成"。

from collections import deque

def topologicalsortkahn(graph, n): in_degree = [0] * n for u in range(n): for v in graph[u]: in_degree[v] += 1

queue = deque([v for v in range(n) if in_degree[v] == 0]) result = []

while queue: u = queue.popleft() result.append(u) for v in graph[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v)

if len(result) != n: return None # 存在环，无拓扑序 return result ```

时间复杂度：$O(V + E)$——每个节点和每条边被处理一次。

环检测：若最终 result 长度不等于 $n$，说明存在环（某些节点的入度永远不会变为 0）。

值得注意的是 Kahn 论文里的场景就已经是工业级的：这个方法是他在西屋电气（Westinghouse，Baltimore）为工程项目网络排序时做出来的副产品，论文里报告一张 30000 项活动的 PERT 网络可以在 IBM 7090 上一小时内排完（CACM 5(11), 1962）。

手算一遍：入度表怎么一步步塌下来#

拿一个小型 C 项目的构建依赖图。6 个节点、7 条边：

边（按文件里出现的顺序）：$A\to D$、$A\to B$、$A\to C$、$D\to E$、$B\to E$、$E\to F$、$C\to F$。读法是"左边先完成"：三个 .o 都要先有 config.h；静态库要等 parser.o 和 util.o；最终链接要等静态库和 main.o。

Kahn + FIFO 队列（A 的邻接表按边的出现顺序是 [D, B, C]）：

逐条边验一遍：$A\to D$（1 位 → 2 位）、$A\to B$、$A\to C$、$D\to E$（2 位 → 5 位）、$B\to E$（3 位 → 5 位）、$E\to F$、$C\to F$，全部满足"左边在前" ✅。

这张表最该注意的是第 2 步与第 4 步：出队了，但一个新节点也没入队。入度只从 2 降到 1，说明 E 还欠着另一个前驱。Kahn 算法的全部内容就是"欠债计数"：入度不是图的属性，是一个正在减少的欠账；减到 0 的那一刻就是"这个任务的所有前置条件都齐了"。

换成最小堆，就得到字典序最小的拓扑序：

FIFO 给出 A D B C E F，堆给出 A B C D E F——两者都完全合法，后者恰好是字典序最小的那一个。代价是复杂度从 $O(V+E)$ 变成 $O(V + E\log V)$：每次入队/出队都要维护堆序。

为什么必须用堆而不能"先跑一遍 Kahn 再排序"？因为字典序最小是在线的贪心：每一步都要在"当前所有已就绪的节点"里挑编号最小的，而这个就绪集合本身依赖前面的选择。把 A D B C E F 事后排序只会得到一个非法序列。

拓扑序的唯一性与图的结构#

唯一拓扑序 ↔ 哈密顿路径：若 DAG 的拓扑序唯一，则图中存在一条从第一个节点到最后一个节点经过所有节点的哈密顿路径（即图形成一条"链"）。上面那张构建图显然不唯一——A 之后 B、C、D 三个都就绪，谁先都行。

数一数到底有多少个。约束只有两条：E 必须在 B 和 D 之后，F 必须在 E 和 C 之后。于是 A 恒在首位、F 恒在末位（F 要等 E，E 要等 B 和 D，所以 B、C、D、E 都在 F 前）。剩下 B、C、D、E 四个的排列共 $4! = 24$ 种，其中 E 排在 B 和 D 之后的比例是 $1/3$（在 B、D、E 三者的 $3! = 6$ 种相对顺序里，E 最后的只有 BDE 和 DBE 两种）。所以

$$24 \times \frac13 = 8$$

这张 6 节点小图有 8 个合法的构建顺序。这个数字随图规模爆炸得极快，而且计数问题本身是 #P-完全的——Brightwell 与 Winkler 在 1991 年证明了"计算偏序集的线性扩展个数"是 #P-完全问题（Order 8(3), 225–242），比 NP 更难一档。这是一个很有意思的对照：找一个拓扑序是 $O(V+E)$，数清有多少个却几乎不可能。

字典序最小拓扑排序：如上一节所述，Kahn 算法中把普通队列换成最小堆即可。

失败现场：有环的时候会发生什么#

给上面那张图加一条荒谬但真实世界常见的边：$F \to D$（可执行文件"依赖"了工具库，比如有人在 util.c 里 #include 了链接期才生成的东西）。现在 D 的入度变成 2，图里出现了环 $D \to E \to F \to D$。

Kahn 算法这样死掉：

队列干涸，输出只有 3 个节点。剩下的 D、E、F 残留入度各为 1——它们正好就是那个环。这不是巧合：一个节点走不出去，只能是因为它的某个前驱也走不出去；顺着这条链回溯必然回到自身，也就是环。

于是环检测就有了免费的定位能力，真实工具正是这么报错的：

• Go 编译器直接拒绝：import cycle not allowed，并把整条环上的包名列出来。Go 的包初始化顺序就是依赖图的拓扑序，有环则顺序不存在，所以这是语言层面的硬约束而非风格建议。
• Excel 会弹出"一个或多个循环引用"的警告并给出定位工具。它的引擎维护一棵依赖树（dependency tree）和一条计算链（calculation chain）：单元格改动后，所有直接与间接依赖它的格子被标记为 dirty，再按计算链的顺序重算。若某个格子直接或间接依赖自己，链就不存在——Excel 检测到并报错（微软官方文档 Excel Recalculation 有完整描述）。
• 包管理器与构建工具（make、Gradle、CMake）在遇到循环依赖时拒绝继续，因为"先做哪个"这个问题没有答案。

该记住的是："检测到环"和"找不到拓扑序"是同一件事的两种说法，而残留的非零入度节点集合就是环所在的位置。不需要另写一个环检测算法。

DFS 版本#

基于深度优先搜索的拓扑排序：完成 DFS 时，将节点压入栈，最终逆序输出栈中元素即为拓扑序。

直觉：DFS 回溯时，意味着该节点的所有后继都已被"处理"，因此在拓扑序中它应排在所有后继之前——压栈逆序输出正好符合此要求。

def topological_sort_dfs(graph, n):
    color = ['white'] * n  # 未访问/访问中/已完成
    stack = []
    has_cycle = [False]

def dfs(u): color[u] = 'gray' # 访问中 for v in graph[u]: if color[v] == 'gray': # 发现后向边 → 有环 has_cycle[0] = True return if color[v] == 'white': dfs(v) color[u] = 'black' # 已完成 stack.append(u)

for v in range(n): if color[v] == 'white': dfs(v)

return None if has_cycle[0] else stack[::-1] ```

DFS 版本的关键：灰色节点（正在访问中）出现后向边 → 发现环。这是 DFS 环检测的标准方法。

两种方法时间复杂度都是 $O(V + E)$，各有优缺点：Kahn 直接给出拓扑序且易于检测环；DFS 版可以更方便地处理某些需要 DFS 信息的扩展问题。工程上还有一条现实理由偏向 Kahn——DFS 版本的递归深度等于最长路径长度，在一条几万个节点的长链上会栈溢出，必须手工改写成显式栈；Kahn 版本天生是迭代的。

现场：拓扑序不是一条线，是一道锋面#

工程上最容易被漏掉的一层是这个：构建系统真正需要的不是那条线性序列，而是每一时刻"入度为 0 的那个集合"。

回到那张构建图。A 完成之后，B、C、D 三个节点的入度同时降到 0——它们互相之间没有任何依赖，可以同时编译。make -j 干的就是这件事：维护就绪集合，有空闲工作进程就从里面取一个。线性拓扑序只是这道"锋面"逐步推进时留下的一种可能轨迹。

给每个任务加上耗时，就能算出并行的天花板。设 A（生成头文件）1 秒、B 4 秒、C 2 秒、D 3 秒、E（打包静态库）1 秒、F（链接）2 秒：

$ES(v) = \max_{u \to v}\big(ES(u) + \text{dur}(u)\big)$，按拓扑序从左到右一遍填完，$O(V+E)$。

串行做完是 $1+4+2+3+1+2 = 13$ 秒，无限并行是 8 秒——加速比上限只有 1.6 倍，且 -j2 就能达到（核 1 跑 B，核 2 依次跑 D 和 C，都在 E 需要它们之前完成）。再多给核心一点用都没有。

那条决定 8 秒的路径 $A \to B \to E \to F$ 就是关键路径（Critical Path）——松弛为 0 的任务串。C 有 3 秒松弛，意味着 main.o 编译慢 3 秒也不会拖慢整体；而 B 慢 1 秒，整个构建就慢 1 秒。这是"为什么我加了 32 核构建还是这么慢"最常见的答案：瓶颈不在核心数，在依赖图的深度。

同一套结构在别处反复出现：Apache Spark 的 DAGScheduler 把 RDD 血缘图在 shuffle 边界切成 stage，一个 stage 只有在它依赖的全部 stage 算完后才被提交——这就是 stage 层面的拓扑序，而互不依赖的 stage 可以并发执行。现代构建系统（Bazel 一类）把这件事做到极致：动作图的每个节点声明完整输入，于是就绪集合可以被分发到成百上千台机器上。

破除误解：包管理器做的远不只是拓扑排序#

"apt/npm 用拓扑排序装包"这句话只说对了后半程。

拓扑排序回答的是"顺序"：版本已经定了，按依赖关系排出安装次序。这是 $O(V+E)$ 的多项式问题。

但包管理器面对的真正难题是"选哪个版本"：A 要 C >= 2.0，B 要 C < 2.0，D 声明与 E 冲突，某个虚包可以由三个实包中任一个提供。这是一个带析取与否定的约束满足问题，它是 NP-完全的——EDOS 项目在 2005 年为 Debian 与 RPM 的依赖语言分别给出了 3SAT 归约的证明（Di Cosmo 等），归约用到的正是"一个依赖可以列多个候选"这个特性（Debian 的 | 语法、RPM 的 Provides）。

所以现代包管理器的内核其实是 SAT 求解器：

• libsolv（openSUSE 开发，被 dnf、zypper、Conda、Mamba 使用）实现了带监视文字的 CDCL——与 MiniSat 同一套核心算法，另加针对包管理的领域优化。
• Sat4j 被 Eclipse 用于插件安装的依赖求解。
• PubGrub（源自 Dart 的 pub）是冲突驱动子句学习的一个变体，把通用子句换成版本区间与"不兼容记录"，好处是失败时能给出人能读懂的解释，而不是一句"无解"。
• Go 的最小版本选择（Minimal Version Selection）走的是另一条路：改变依赖语义本身，让求解过程变成确定性的、多项式时间的，代价是放弃"自动取最新兼容版本"。

而 apt 长期以来用的是启发式加回溯，这也是它偶尔给出奇怪方案或干脆放弃的原因——文献里明确指出它的策略并不完备。

该记住的判断：拓扑排序解决的是"排序"，不是"选择"。看到一个依赖系统，先分清它面对的是哪一个——前者是 $O(V+E)$，后者是 NP-完全，误判会让你对着一个 SAT 问题优化图遍历。

重要应用#

构建系统与包管理#

Make、Gradle、CMake：编译项目时，源文件之间有依赖关系（A.cpp 需要 B.h 中的类型定义）。构建工具用拓扑排序确定编译顺序，只重新编译需要更新的文件。

npm、pip、Maven：软件包 A 依赖包 B、B 依赖包 C——包管理器用拓扑排序确定安装顺序，并检测循环依赖（若存在循环，安装无法完成）。版本选择那一半的难度见上一节。

课程规划#

大学课程体系：线性代数是机器学习的先修课，微积分是线性代数的先修课……拓扑排序给出合理的学习顺序。（Kahn 1962 年论文的原始应用并非课程规划，而是工程项目网络——他在 Westinghouse 用它对 PERT 网络中数万项活动排序。）

关键路径分析（CPM/PERT）#

工程项目中，每个任务有完成时间，任务间有依赖关系。关键路径（Critical Path）是从项目开始到结束的最长路径（决定项目最短工期）。

计算关键路径：对 DAG 拓扑排序后，用动态规划计算每个节点的"最早开始时间"——在 DAG 上的"最长路径"问题，时间 $O(V + E)$（而一般图上最长路径是 NP-hard 的）。上文那张 $ES$ 表就是一次完整的 CPM 计算。

数据流分析（编译器优化）#

编译器中，程序语句构成数据流图（SSA 形式），拓扑排序用于常量传播、活跃变量分析等优化 pass 的顺序安排。

DAG 上的动态规划#

重要定理：所有 DAG 上的动态规划，都可以通过先拓扑排序、再按序计算实现，无需记忆化递归。

例如 DAG 最短路径：按拓扑序处理节点，每个节点只需看其已处理的前驱——比 Dijkstra 更高效（$O(V + E)$ 而非 $O((V+E) \log V)$），且能处理负权边（因 DAG 无环，无负权环问题）。

检测有向环#

拓扑排序的一个重要副产品：判断有向图是否有环。

• Kahn 算法：若输出长度 $< n$ → 有环，且残留入度非零的节点集合就是环的所在
• DFS 算法：若发现灰色节点的后向边 → 有环，且当前递归栈上从该灰点起的那一段就是环本身
• 时间复杂度：$O(V + E)$

这比其他环检测方法（如 Floyd 判圈，用于链表）更适合稀疏图。想报出"具体是哪个环"时 DFS 版更方便，因为递归栈天然记录了路径。

跨域连接#

• 组合数学：拓扑序就是偏序集的线性扩展，于是"有多少种合法顺序"变成一个纯计数问题。而这里有一处刺眼的反差：找出一个顺序是线性时间，数清有多少个却被证明属于比 NP 更难的一档。求一个解与数全部解的代价，可以差得这么远。
• 因果：有向无环图同时是因果结构的标准表示，无环正是"原因先于结果"的形式化。一旦出现环，"先算谁"与"谁导致谁"同时失去定义——所以构建工具报出循环依赖、因果模型拒绝有环，本质上是同一条约束在两个领域的表现。
• 细胞周期：检查点做的正是入度归零的事：前一阶段的全部条件满足，才允许进入下一阶段。有意思的是细胞周期本身是循环的，靠若干不可逆的降解步骤把环打断，从而在每一轮内部重建一个可排序的顺序——生物系统解决环的办法，是让某些边只能走一次。
• GPU 与并行计算：真正有用的往往不是那条线性序列，而是每一时刻入度为零的那个集合——它们彼此无依赖，可以同时开工。加速比的上限由依赖图的深度决定，而不是核心数："加了很多核为何还是慢"的答案通常写在关键路径上。
• SAT 求解：包管理常被说成靠拓扑排序，这只说对了后半程。排顺序是多项式问题；而在版本区间、冲突与可替代提供者之间选出一组可行版本，是 NP 完全的。所以现代包管理器的内核其实是冲突驱动的子句学习求解器，看清面对的是哪一半，才不会对着难题优化图遍历。

参考文献#

• Kahn, A.B. "Topological Sorting of Large Networks." Communications of the ACM 5(11), 558–562, 1962.
• Brightwell, G. & Winkler, P. "Counting Linear Extensions." Order 8(3), 225–242, 1991.（线性扩展计数的 #P-完全性）
• Mancinelli, F., Boender, J., Di Cosmo, R., Vouillon, J., Durak, B., Leroy, X. & Treinen, R. "Managing the Complexity of Large Free and Open Source Package-Based Software Distributions." ASE 2006, 199–208.（EDOS 项目：Debian/RPM 依赖求解的 NP-完全性与 apt 启发式的不完备性）
• Microsoft. Excel Recalculation.（依赖树、计算链、dirty 标记与循环引用检测的官方说明）
• Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022.（第 20 章 Elementary Graph Algorithms，22 章 DFS 与拓扑排序）

延伸阅读#

• Kleinberg, J. & Tardos, É. Algorithm Design. Pearson, 2005.（第 3 章 Graphs，拓扑排序与 DAG 的标准教学处理）
• Knuth, D.E. The Art of Computer Programming, Vol. 1. 3rd ed. Addison-Wesley, 1997.（2.2.3 节给出了拓扑排序最早的系统化叙述之一）
• Abate, P., Di Cosmo, R., Gousios, G. & Zacchiroli, S. "Dependency Solving Is Still Hard, but We Are Getting Better at It." SANER 2020, 547–551. DOI 10.1109/SANER48275.2020.9054837.（十五年后的现状回顾与各包管理器求解能力普查）
• Apache Spark 官方文档中的 Job / Stage / Task 调度章节，可对照看 DAG 调度在数据系统里的形态。