拓扑排序与 DAG：有依赖时的合法顺序

上一篇我们用 DFS 的 low-link 值分析了图的连通结构——连通分量、桥、割点、SCC。在 SCC 缩点那一节，我们发现了一个关键事实：缩点后的图一定是 DAG。这个 DAG 有什么用？这正是本文的起点。

在 Part 1”探”的第三站，我们聚焦于一类特殊但极其重要的图——有向无环图（DAG, Directed Acyclic Graph）。现实中大量问题天然具有”依赖”结构：编译器需要按依赖顺序编译模块、构建系统（Make/Bazel）需要确定编译目标的合法执行顺序、大学课程有先修要求、电子表格需要按公式依赖顺序计算单元格、项目经理需要找出最早完成时间。没有拓扑排序，你无法为任何带依赖关系的任务找到一个合法的执行顺序。 更进一步，DAG 的无环性质使得最短路径和最长路径都能在 $O(V + E)$ 时间内求解——比一般图上的 Dijkstra 或 Bellman-Ford 快得多。

算法范式：穷举搜索（DFS 后序反转、Kahn’s BFS）、动态规划（DAG 最短/最长路径——按拓扑序松弛）

核心概念：什么是 DAG？

有向无环图（DAG） 的定义非常简单：一个有向图 $G = (V, E)$ ，其中不存在任何有向环（directed cycle）。换句话说，不存在从某个节点 $v$ 出发沿有向边走一圈回到 $v$ 的路径。

DAG 拥有一个关键的等价性质，这是本文的核心定理：

定理：有向图 $G$ 是 DAG $\Leftrightarrow$ $G$ 存在拓扑排序（topological ordering）。

拓扑排序（topological sort / topological ordering）是 DAG 的所有节点的一个线性排列 $v_1, v_2, \ldots, v_n$ ，使得对于每条有向边 $(v_i, v_j) \in E$ ， $v_i$ 都排在 $v_j$ 之前（即 $i < j$ ）。

直觉上：把所有节点排成一条线，所有边都”从左指向右”。

证明（双向）：

DAG → 存在拓扑排序：DAG 中一定存在入度为 0 的节点（否则从任意节点出发，沿入边反向追溯，经过有限步一定重复——形成环，与 DAG 矛盾）。取出入度为 0 的节点，删除它及其出边，剩余图仍是 DAG，递归地继续。这恰好是 Kahn’s 算法的正确性证明。
存在拓扑排序 → DAG：如果有环 $v_{a_1} \to v_{a_2} \to \cdots \to v_{a_k} \to v_{a_1}$ ，则在拓扑排序中 $v_{a_1}$ 必须同时排在 $v_{a_2}$ 之前和之后，矛盾。

这个等价关系意味着：拓扑排序不仅是 DAG 的一个有用操作，它还是 DAG 的特征刻画（characterization）——一个有向图能被拓扑排序，当且仅当它无环。

两种拓扑排序算法

拓扑排序有两种经典实现，时间复杂度都是 $O(n + m)$ （ $n = |V|$ , $m = |E|$ ），但思路截然不同。

方法一：DFS 后序反转

核心思想：对 DAG 做 DFS，记录节点的”完成时间”。由于 DAG 无环，DFS 不会遇到回边（如果遇到灰色节点就说明有环）。对于每条边 $(u, v)$ ， $u$ 一定在 $v$ 之后完成（因为 $u$ 要等 $v$ 的子树全部完成才能完成自己）。因此，后序的反转就是拓扑排序。

DFS-Toposort(G):
    order = empty list
    for each v ∈ V:
        if not visited[v]:
            DFS-Visit(v, order)
    return reverse(order)

DFS-Visit(u, order):
    visited[u] = true
    for each (u, v) ∈ E:
        if not visited[v]:
            DFS-Visit(v, order)
    order.append(u)    // 后序：所有后代都已处理

正确性论证：对于 DAG 中的任意边 $(u, v)$ ，在 DFS 中有两种情况：

$v$ 在 $u$ 之前被发现：此时 $v$ 在 $u$ 的 DFS 子树中， $v$ 先于 $u$ 完成。
$v$ 在 $u$ 之前就已经完成了： $v$ 的完成时间 < $u$ 的完成时间。

两种情况下 $v$ 都先于 $u$ 完成 → 后序中 $v$ 排在 $u$ 前面 → 反转后 $u$ 排在 $v$ 前面 ✓。

复杂度：时间 $O(n + m)$ （一次 DFS），空间 $O(n)$ （递归栈 + visited 数组）。

方法二：Kahn’s BFS（入度法）

Arthur Kahn 在 1962 年提出了一种直觉更直接的算法，基于入度（in-degree， $\deg^-(v)$ ）的概念：

核心思想：不断找到”没有前驱”的节点（ $\deg^-(v) = 0$ ），输出它，然后”删掉”它——把它的所有出边去掉，可能产生新的入度为 0 的节点。重复直到所有节点都被输出。

Kahn-Toposort(G):
    compute deg⁻(v) for all v ∈ V
    queue Q = {v : deg⁻(v) = 0}
    order = empty list

    while Q is not empty:
        u = Q.dequeue()
        order.append(u)
        for each (u, v) ∈ E:
            deg⁻(v) -= 1
            if deg⁻(v) == 0:
                Q.enqueue(v)

    if |order| < |V|:
        error "Graph has a cycle!"
    return order

逐步解释：

compute deg⁻(v) for all v：遍历所有边，统计每个节点的入边数。 $O(m)$ 。
queue Q = {v : deg⁻(v) = 0}：入度为 0 的节点没有任何前驱依赖，可以安全地排在最前面。
deg⁻(v) -= 1：相当于”虚拟删除”边 $(u, v)$ —— $u$ 已经被输出，它不再是 $v$ 的阻碍。
if deg⁻(v) == 0： $v$ 的所有前驱都已经被输出了， $v$ 现在可以安全输出。
if |order| < |V|：如果队列提前为空但还有节点没被输出，说明存在环——环中的节点互相等待，入度永远降不到 0。

复杂度：时间 $O(n + m)$ （每个节点入队出队一次，每条边处理一次），空间 $O(n)$ （入度数组 + 队列）。

Kahn’s 算法走查

下面的交互组件展示 Kahn’s 算法在一个 7 节点 DAG 上的完整执行过程。注意观察入度值的变化和队列的内容。

Kahn's 算法走查步骤 1 / 25

队列

（空）

拓扑序（输出）

（空）

初始状态：计算每个节点的入度。A 和 B 的入度为 0——它们没有前驱。

观察几个关键时刻：

初始时 A 和 B 的入度都为 0，它们被同时入队——谁先出队取决于队列实现，这正是拓扑排序不唯一的原因。
D 的入度为 2（A→D 和 B→D），必须等 A 和 B 都被处理后才能降为 0。
最终所有 7 个节点都被输出，确认图无环。

拓扑排序不唯一

一个 DAG 通常有多个合法的拓扑排序。

关键观察：如果两个节点之间没有（直接或间接的）依赖关系，它们的相对顺序可以是任意的。Kahn’s 算法中，同时入度为 0 的节点的出队顺序就决定了具体的排列。在 DFS 方法中，选择哪个未访问节点先开始 DFS 也会影响结果。

唯一拓扑排序的条件：当且仅当拓扑排序的每一步恰好只有一个入度为 0 的节点。等价地，DAG 中存在一条包含所有节点的有向路径（哈密顿路径）。这在实践中很少见。

两种方法对比

维度	DFS 后序反转	Kahn’s BFS
时间复杂度（最坏）	$O(n + m)$	$O(n + m)$
空间复杂度	$O(n)$	$O(n)$
环检测	DFS 中遇到灰色节点即有环	输出节点数 < $n$ 即有环
直觉	利用 DFS 后序的时间戳性质	”不断剥离没有前驱的节点”
并行化	较难	天然可并行：每批入度为 0 的节点可以同时处理
常见用途	与 DFS 其他操作（SCC、桥等）组合	独立使用，特别是需要并行调度时

环检测：拓扑排序的副产品

拓扑排序和环检测是一枚硬币的两面——能拓扑排序就无环，不能就有环。

DFS 方法：维护三种颜色状态——白色（未访问）、灰色（正在处理，在递归栈上）、黑色（已完成）。如果从灰色节点 $u$ 的 DFS 中发现一条边指向另一个灰色节点 $v$ ，这就是一条回边（back edge），意味着存在 $v \to \cdots \to u \to v$ 的环。

Kahn’s 方法：执行 Kahn’s 拓扑排序，如果最终输出的节点数少于 $n$ ，则图有环。剩余的节点就是参与环的节点（它们的入度永远降不到 0）。

两种方法时间复杂度都是 $O(n + m)$ 。Kahn’s 方法的优势是能直接告诉你”哪些节点参与了环”。

DAG 上的最短路径和最长路径

DAG 的无环性带来一个巨大的计算优势：按拓扑序遍历节点、逐一松弛边，就能在 $O(n + m)$ 时间内求出从源点到所有节点的最短（或最长）路径。这比 Dijkstra 的 $O((n+m)\log n)$ 和 Bellman-Ford 的 $O(nm)$ 都快，而且可以处理负权边。

算法框架

DAG-Shortest-Path(G, s):
    topo_order = Toposort(G)
    d[v] = ∞ for all v; d[s] = 0

    for each u in topo_order:
        for each (u, v) ∈ E:
            if d[u] + w(u,v) < d[v]:        // 松弛
                d[v] = d[u] + w(u,v)
                prev[v] = u
    return d, prev

对于最长路径，只需将比较方向反转：

DAG-Longest-Path(G, s):
    topo_order = Toposort(G)
    D[v] = -∞ for all v; D[s] = 0

    for each u in topo_order:
        for each (u, v) ∈ E:
            if D[u] + w(u,v) > D[v]:        // 松弛（取 max）
                D[v] = D[u] + w(u,v)
                prev[v] = u
    return D, prev

为什么拓扑序松弛是正确的？

关键洞察：在拓扑序中，当我们处理节点 $u$ 时， $u$ 的所有前驱都已经被处理过了。因此 $d[u]$ 已经是最终最优值——不会再有其他路径能更新它。这意味着我们用 $d[u]$ 去松弛 $u$ 的出边时，松弛是基于正确的值进行的。

换一种理解方式：这其实是动态规划。定义子问题 $d[v]$ 为从 $s$ 到 $v$ 的最短路径长度。转移方程：

$d[v] = \min_{(u, v) \in E} \bigl(d[u] + w(u, v)\bigr)$

拓扑序保证了在计算 $d[v]$ 时，所有 $d[u]$ （ $u$ 是 $v$ 的前驱）都已经计算完毕。这正是 DP 的子问题排序要求。

数值走查

在上图的 6 节点加权 DAG 上，拓扑序为 S, A, B, C, D, T。逐步松弛：

最短路径（ $d$ ，初始 $d[S] = 0$ ，其余 $\infty$ ）：

处理节点	松弛边	更新	当前 $d$
S	S→A(3), S→B(2)	$d[A]=3, d[B]=2$	[0, 3, 2, ∞, ∞, ∞]
A	A→C(6), A→D(2)	$d[C]=9, d[D]=5$	[0, 3, 2, 9, 5, ∞]
B	B→D(7)	$d[D]=\min(5, 2+7)=5$ （不更新）	[0, 3, 2, 9, 5, ∞]
C	C→T(1)	$d[T]=10$	[0, 3, 2, 9, 5, 10]
D	D→T(3)	$d[T]=\min(10, 5+3)=8$	[0, 3, 2, 9, 5, 8]

最短路径 S→T = 8，路径 S→A→D→T（3+2+3）。

最长路径（ $D$ ，初始 $D[S] = 0$ ，其余 $-\infty$ ）：

处理节点	松弛边	更新	当前 $D$
S	S→A(3), S→B(2)	$D[A]=3, D[B]=2$	[0, 3, 2, -∞, -∞, -∞]
A	A→C(6), A→D(2)	$D[C]=9, D[D]=5$	[0, 3, 2, 9, 5, -∞]
B	B→D(7)	$D[D]=\max(5, 2+7)=9$	[0, 3, 2, 9, 9, -∞]
C	C→T(1)	$D[T]=10$	[0, 3, 2, 9, 9, 10]
D	D→T(3)	$D[T]=\max(10, 9+3)=12$	[0, 3, 2, 9, 9, 12]

最长路径 S→T = 12，路径 S→B→D→T（2+7+3）。

关键对比：同一个框架、同一个图、同一个拓扑序，只是松弛时 min/max 不同，就能分别求出最短和最长路径。而且时间复杂度都是 $O(n + m)$ 。

注意：一般有向图上的最长路径问题是 NP-hard 的（等价于哈密顿路径问题），但 DAG 上的最长路径可以在多项式时间内求解。这是 DAG 的无环性带来的巨大简化。

为什么 DAG 上能处理负权边？

Dijkstra 算法无法处理负权边，因为它依赖”已确定的节点不会再被更新”的贪心假设——负权边可以打破这个假设。但 DAG 的拓扑序天然保证了”处理节点 $u$ 时它的最优值已确定”，不依赖贪心假设，因此负权边完全不影响正确性。

关键路径法（Critical Path Method）

DAG 最长路径的一个重要应用是关键路径法（CPM, Critical Path Method），广泛用于项目管理。

问题建模

一个项目包含若干任务（activities），每个任务有一个持续时间（duration）。任务之间有先后依赖：某些任务必须在另一些任务完成后才能开始。问：项目的最短完成时间是多少？哪些任务是”关键”的——它们的任何延迟都会直接导致项目延期？

建模为 DAG：

节点 = 任务
边 = 依赖关系（ $u \to v$ 表示 $v$ 依赖 $u$ ）
节点权重 = 任务持续时间

CPM 算法

CPM 实质上就是 DAG 上的最长路径问题。具体分为两个 pass：

Forward Pass（正向遍历）——按拓扑序计算每个任务的最早开始时间（ES, Earliest Start）和最早完成时间（EF, Earliest Finish）：

$\text{ES}[v] = \max_{(u, v) \in E} \text{EF}[u], \quad \text{EF}[v] = \text{ES}[v] + \text{dur}[v]$

直觉：一个任务的最早开始时间 = 它所有前驱任务中最晚完成的那个。

Backward Pass（反向遍历）——按拓扑序的逆序计算每个任务的最迟开始时间（LS, Latest Start）和最迟完成时间（LF, Latest Finish）：

$\text{LF}[v] = \min_{(v, w) \in E} \text{LS}[w], \quad \text{LS}[v] = \text{LF}[v] - \text{dur}[v]$

直觉：一个任务的最迟完成时间 = 它所有后继任务中最早需要开始的那个。

松弛时间（Slack）： $\text{Slack}[v] = \text{LS}[v] - \text{ES}[v]$

$\text{Slack}[v] = 0$ 的任务在关键路径上——它们没有任何缓冲，任何延迟都会延迟整个项目。
$\text{Slack}[v] > 0$ 的任务有余量，可以适度延迟而不影响项目工期。

项目最短完成时间 = 从 Start 到 End 的 DAG 最长路径 = $\text{EF}[\text{End}]$ 。

复杂度：Forward + Backward 各一次拓扑序遍历， $O(n + m)$ 。

与 Art. 2 的连接：SCC 缩点 + 拓扑排序

上一篇的 SCC 缩点操作和本文的拓扑排序是天然的组合。当你面对的不是 DAG 而是一般有向图（可能有环）时，处理流程是：

Tarjan / Kosaraju： $O(n + m)$ 找出所有 SCC
缩点：将每个 SCC 缩成一个超级节点，得到 DAG
拓扑排序：在缩点 DAG 上做拓扑排序

这个”SCC 缩点 → 拓扑排序”的模式在很多问题中反复出现：

2-SAT 求解（Art. 2 已介绍）：蕴含图 → SCC → 缩点 DAG → 按拓扑序的反序赋值
编译器循环依赖处理：模块依赖图 → SCC 找出循环依赖组 → 缩点后按拓扑序编译
有向图可达性：缩点后在 DAG 上做可达性分析更高效

应用场景

拓扑排序和 DAG 算法在工程实践中无处不在。它们的共同模式是：实体 + 先后依赖 → 建 DAG → 拓扑排序（或 DAG DP）→ 合法执行顺序（或最优路径）。

编译器依赖分析与指令调度

编译系统（Make、Bazel、Gradle、Cargo）的核心问题：给定源文件之间的依赖关系，确定编译顺序。每个源文件或编译目标（target）是 DAG 的节点，#include 或 import 关系是边。拓扑排序给出合法编译序，关键路径决定了最短编译时间。

实例：Bazel 和 Buck 将整个构建图建模为 DAG，自动并行执行没有依赖关系的目标（相当于 Kahn 算法中同时入度为 0 的节点）。这是 Kahn 天然可并行化的直接应用。

在编译器内部，指令调度（instruction scheduling）同样基于 DAG：每条指令是节点，数据依赖是边，调度器按拓扑序安排指令执行顺序，同时利用 CPM 找出关键路径以最小化延迟。

构建系统（Make / Bazel）

make 的 Makefile 本质上定义了一个依赖 DAG。当你执行 make target 时，Make 对依赖图做拓扑排序，确定哪些文件需要重新编译以及编译的顺序。如果依赖图有环，Make 会报错——这就是环检测的实际应用。

课程先修关系

大学课程体系是典型的 DAG：微积分 → 线性代数 → 概率论 → 机器学习。拓扑排序给出合法的选课顺序。如果你想尽快修完机器学习，关键路径告诉你最短需要几个学期。

电子表格公式计算顺序

Excel/Google Sheets 中，单元格之间的公式引用构成 DAG（C1 = A1 + B1，D1 = C1 * 2）。电子表格引擎对这个 DAG 做拓扑排序，确定计算顺序——保证每个单元格在被引用之前已经计算完毕。如果出现循环引用（ $A1 = B1$ , $B1 = A1$ ），引擎检测到环并报错。

项目管理（CPM/PERT）

如前所述，CPM 用 DAG 最长路径解决项目调度问题。PERT（Program Evaluation and Review Technique）是 CPM 的概率版本，用三时估计（乐观、最可能、悲观）处理不确定性。美国海军在 1950 年代用 PERT 管理北极星导弹项目，成功将项目工期缩短了两年。

复杂度对比表

算法	时间复杂度（最坏）	空间复杂度	适用场景
DFS 拓扑排序	$O(n + m)$	$O(n)$	拓扑排序 + 环检测
Kahn’s 拓扑排序	$O(n + m)$	$O(n)$	拓扑排序 + 环检测 + 并行调度
DAG 最短路径	$O(n + m)$	$O(n)$	DAG 上单源最短路，可处理负权边
DAG 最长路径	$O(n + m)$	$O(n)$	DAG 上最长路径（一般图为 NP-hard）
关键路径法（CPM）	$O(n + m)$	$O(n)$	项目调度（正向 + 反向两趟）

所有算法都是线性时间。DAG 的无环性是这一切高效性的根源——它保证了拓扑序的存在，而拓扑序保证了一次遍历就能确定最优值。

🔁 迭代机器视角 — Kahn's algorithmSTR: 结构计算

Graph	DAG
State[v]	入度计数 + 输出序列
SELECT	入度为零的节点（类似 BFS）
COMBINE	删除边 → 更新入度
重入	无
TERMINATE	Frontier 空
求解方法	FI

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — DFS-based topo sortSTR: 结构计算

Graph	DAG
State[v]	visited + 完成时间
SELECT	LIFO (DFS)
COMBINE	DFS 后序反转
重入	无
TERMINATE	所有节点已访问
求解方法	FI

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文展示了 DAG 这一看似简单的结构所蕴含的算法力量：

核心等价：有向图无环 $\Leftrightarrow$ 存在拓扑排序——这不只是一个定理，而是将”依赖关系”转化为”线性顺序”的根本保证
两种拓扑排序：DFS 后序反转（利用时间戳）和 Kahn’s BFS（入度削减）——时间复杂度相同，Kahn 更直观且天然可并行
环检测是副产品：拓扑排序不成功 = 有环
DAG DP：按拓扑序松弛可在 $O(V+E)$ 时间内求最短路/最长路——比 Dijkstra 和 Bellman-Ford 更快，且能处理负权边
关键路径法：DAG 最长路径在项目管理中的直接应用
SCC 缩点 → DAG → 拓扑排序：处理一般有向图的标准流程

DAG 保证了无环——所有的边都”向前”指，所有的依赖都能被线性排序。但如果图有环呢？环带来了截然不同的问题：你能从一个节点出发沿着边走回原地，形成一条闭合回路。下一篇 Art. 4: 欧拉路径与哈密顿路径将探讨这个方向——不是”如何避免环”，而是”如何利用特殊的环结构”，追问一些古老而迷人的问题：你能否恰好经过每条边一次？每个节点一次？

实现指引

算法	库	函数/方法
拓扑排序	NetworkX	`nx.topological_sort(G)`
拓扑排序（所有）	NetworkX	`nx.all_topological_sorts(G)`
拓扑排序（分层）	NetworkX	`nx.topological_generations(G)`
环检测	NetworkX	`nx.is_directed_acyclic_graph(G)`
DAG 最短路径	NetworkX	`nx.shortest_path(G, source, weight='weight')`
DAG 最长路径	NetworkX	`nx.dag_longest_path(G)`
DAG 最长路径长度	NetworkX	`nx.dag_longest_path_length(G)`
DAG 祖先/后代	NetworkX	`nx.ancestors(G, node)`, `nx.descendants(G, node)`
拓扑排序	igraph	`g.topological_sorting()`
环检测	igraph	`g.is_dag()`