5.4 DAG 的拓扑排序

动机

很多调度问题并不要求一个数值最优解，而是要找到任意一个合法顺序。修读 某门课程前要先完成所有先修课；编译某个模块前要先处理它依赖的模块；穿鞋前 要先穿袜子。有些任务之间没有依赖，它们的先后次序就可以交换。

有向图恰好能够表达这种约束：顶点代表任务，边 u->v 表示 u 必须排在 v 前面。拓扑排序把每条局部先后关系整合成一个全局线性序列。我们需要回答 四个问题：顺序何时存在、为什么可能不唯一、怎样高效构造，以及算法失败时 如何确认图中存在有向环。

Tutorial 10 给出两个互补视角。Kahn 算法从“全部前置条件已经满足”的 顶点开始向前构造；DFS 方法等到顶点完成后才将它放进答案，利用反向完成 次序得到结果。两者不只是排序程序，也都能检测有向环。

实际系统往往会把输出顺序交给下一个处理阶段，因此漏掉顶点的部分序列并不 是小的格式问题，而是一个无法执行的错误调度。

定义

定义

有向无环图

有向图 G=(V,E) 的每条边都是有顺序的二元组 (u,v)。如果存在 v_0->v_1->...->v_k->v_0，图中就有一个有向环。没有任何有向环的有向图 称为有向无环图（directed acyclic graph，DAG）。

方向不能忽略。u->v 是从 u 指向 v 的单向约束，并不自动包含反方向。 因此，无向图中的环与这里讨论的有向环不是同一个概念。

定义

拓扑序

G=(V,E) 的拓扑序是一个恰好包含每个顶点一次的序列，而且对于每条边 u->v，u 都出现在 v 之前。如果 pos(x) 表示位置，那么每条边都必须 让 pos(u) 严格小于 pos(v)。

拓扑序不一定唯一。如果 x 和 y 之间不存在任一方向的可达关系，图可能没 有规定它们谁先谁后。算法遇到多个同时合法的选择时，不同的 tie-breaking 会 产生不同但同样正确的答案。拓扑排序寻找的是满足约束的一个顺序，而不是必然 唯一的顺序。

定义

入度、源点与邻接表

indegree[v] 是进入 v 的边数；入度为零的顶点称为源点。邻接表 adj[u] 只列出所有由 u 指向的后继顶点。

两种算法都需要从已处理顶点沿出边前进，所以邻接表比每次扫描邻接矩阵的一整 行更合适。DFS 检测环时还要区分三种状态：未标记、位于当前递归路径上的临时 标记，以及连同全部后继都已完成的永久标记。遇到临时标记意味着一条边返回 当前路径上的祖先，从而闭合为有向环。

定理 / 命题

定理

拓扑序存在当且仅当图是 DAG

有向图如果包含有向环，就不存在拓扑序；反过来，每个有限 DAG 都至少有一个 拓扑序。

关键结构事实是：每个非空有限 DAG 都有源点。假如每个顶点都有入边，任选一 点并不断沿入边反向前进；由于顶点数有限，最终一定重复某个顶点并形成有向 环。因此 DAG 必然有一个可以安全放在首位的源点；移除它后剩余图仍是 DAG， 于是可以重复同一论证。

定理

Kahn 算法的处理数判据

Kahn 算法输出全部 |V| 个顶点，当且仅当输入图是 DAG。如果零入度容器已 空，但输出数 k 小于 |V|，未处理子图中必然存在有向环。

所以实现不能把部分序列当作成功结果；必须比较已输出数量与总顶点数。

定理

反向 DFS 完成次序是拓扑序

如果 DFS 没有遇到指向临时标记顶点的边，每个顶点完成时将它加入答案最前端， 最终序列就是一个拓扑序。

这里必须使用完成时刻，而不是首次发现时刻。另一种等价写法是在完成时 push 进 stack，并在整个 DFS 结束后反转。

证明思路

为什么有向环不可能排序

假设存在环 v_0->v_1->...->v_k->v_0。每条边都要求下一个位置严格更大， 沿环走一圈就会要求 pos(v_0) 严格小于自己，产生矛盾。这不仅是说某幅图 里碰巧有一支箭向左，而是任何线性排列都至少违反环上的一条边。

Kahn 不变量与正确性

维护不变量：indegree[v] 等于尚未输出的顶点指向 v 的边数。开始时 扫描所有边一次计算入度；输出 u 时只扫描 adj[u]，并将每个后继的入度减 一。某个顶点第一次降为零，恰好说明它的全部前驱已经输出，因此把它接到答案 末尾不会违反任何边。

KAHN(adj, V):
    indegree[v] = 0 for every v
    for each u in V:
        for each v in adj[u]: indegree[v] += 1
    S = all v with indegree[v] == 0
    order = empty list
    while S is not empty:
        remove one u from S
        append u to order
        for each v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0: insert v into S
    if length(order) != |V|: return error directed cycle
    return order

如果仍有顶点而 S 已空，剩余有限子图没有源点；根据上述结构事实，它不可 能是 DAG。S 可以用 queue、stack、set 或 priority queue；选择只影响返回 哪一个合法顺序，不影响正确性。

DFS 标记、完成逻辑与正确性

临时标记的顶点恰好组成当前 recursion stack。如果 u->v 指向临时标记的 v，stack 已经给出路径 v->...->u，新边把它闭合成环。指向永久标记则是 安全的，因为 v 已完成并且已经放入答案。

若没有环，考虑任意边 u->v。当 u 准备完成时，v 要么由这次 DFS 递归 完成，要么之前已经永久完成；两种情况下 v 都已在答案中。此时把 u 加到 最前面，就保证 u 位于 v 之前。这个论证适用于每条边。

DFS-TOPO(adj, V):
    mark[v] = UNMARKED for every v
    order = empty list
    for each v in V:
        if mark[v] == UNMARKED: VISIT(v)
    return order

VISIT(u):
    if mark[u] == TEMPORARY: abort with error directed cycle
    if mark[u] == PERMANENT: return
    mark[u] = TEMPORARY
    for each v in adj[u]: VISIT(v)
    mark[u] = PERMANENT
    add u to the front of order

邻接表复杂度

Kahn 初始化数组并寻找源点需要 O(V)；计算与更新入度时，每个邻接表条目 只被扫描常数次，共 O(E)，所以 queue 或 stack 版本的总时间是 O(V+E)。 DFS 同样只启动每个顶点一次、检查每条出边一次，因此也是 O(V+E)。两者在 图存储之外都需要 O(V) 辅助空间。若改用邻接矩阵，每个顶点都要扫描 V 个可能邻居，即使图很稀疏也需要 O(V^2) 时间。

例题详解

例题

检查顺序并观察非唯一性

Tutorial 10 的图包含边 A->B, A->D, B->C, B->D, C->D, C->E, C->F, D->E。 A,B,C,D,E,F 与 A,B,C,D,F,E 都合法，因为没有边限制 E 与 F 的 相对次序。A,B,C,E,D,F 不合法，因为 D->E 的尾端反而更晚。检查拓扑 序时必须检查所有图边，不能只看序列中的相邻顶点。

例题

Tutorial 10 图的完整 Kahn trace

初始入度为 A:0, B:1, C:1, D:3, E:2, F:1。按照 tutorial 中的分支选 择，状态如下：

步骤	取出	入度更新	随后可选	输出
起点	—	—	{A}	空
1	A	B:1->0, D:3->2	{B}	A
2	B	C:1->0, D:2->1	{C}	A,B
3	C	D:1->0, E:2->1, F:1->0	{D,F}	A,B,C
4	F	无	{D}	A,B,C,F
5	D	E:1->0	{E}	A,B,C,F,D
6	E	无	空	A,B,C,F,D,E

六个顶点全部输出，因此结果有效。第三步之后也可以先选 D；这个分支就是 多个拓扑序的具体来源。

例题

同一幅图的完整 DFS 完成 trace

从 B 开始，并按照 tutorial 的 F,E,D 次序检查 C 的后继。完成事件依 次把前置答案变为：

完成顶点	加到最前后的答案
F	F
E	E,F
D	D,E,F
C	C,D,E,F
B	B,C,D,E,F

外层循环随后遇到未标记的 A；它的后继 B,D 已永久完成，所以 A 可以 直接完成并加到最前，得到 A,B,C,D,E,F。加入最前的次序与完成次序相反。

例题

两种方法怎样揭示同一个环

在 tutorial 图中加入 E->B，就得到 B->C->E->B（同时也存在更长的 B->C->D->E->B）。Kahn 只能移除 A，随后还有五个顶点但不存在零入 度点，因此报告有环。DFS 从 B 临时标记 C，先完成 F，再按既定的 F,E,D 次序临时标记 E；当 E 指回仍带临时标记的 B 时，立即报告 B->C->E->B。此时 D 还没有被访问。两种方法都不能把部分答案当成成功 排序。

常见错误

常见错误

只检查序列中的相邻顶点

合法性要求每条 u->v 都让 u 更早；并不是大部分箭向前，或者相邻项看起 来合理就足够。

常见错误

每轮重新计算全部入度

应当先计算一次入度，移除 u 时再沿 adj[u] 精确递减。反复扫描全图会破 坏线性时间界限。

常见错误

忘记检查 Kahn 的输出数量

容器为空只有在全部顶点已经输出时才表示成功；否则剩余子图含有环。

常见错误

DFS 只使用一个 visited bit

已经见过的顶点可能仍在当前路径上，也可能早已完成。只有前一种情况证明有 环，因此必须区分临时标记与永久标记。

常见错误

DFS 在发现顶点时就加入答案

正确规则是在完成时加到最前，或者完成时 push 并在最后反转；发现次序没有这 个保证。

总结

• 拓扑序恰好包含每个顶点一次，并且尊重每条有向边。
• 存在拓扑序当且仅当图是 DAG；有向环会产生互相矛盾的先后要求。
• Kahn 维护剩余入度并反复输出零入度点；输出少于 |V| 就证明有环。
• DFS 用未标记、临时、永久三种状态检测环，并用反向完成次序排序。
• 不同 tie-breaking 或 DFS 探索次序可以产生不同但同样合法的答案。
• 使用邻接表时，两种方法都是 O(V+E) 时间和额外 O(V) 空间。

练习

思考检查

1. Tutorial 10 图中，Kahn 先后输出 A、B 后，C、D、E、F 的剩余入度分别是多少？下一个可以选谁？

只更新从已移除顶点发出的边。

思考检查

2. 一个有 9 个顶点的图只输出 7 点后，零入度容器就变为空。Kahn 可以得出什么结论？

比较处理数量与总顶点数。

思考检查

3. DFS 遇到指向永久标记 v 的边 u->v，是否已经证明有环？它与指向临时标记有何区别？

永久标记说明 v 的递归调用已经返回。

思考检查

4. 只有 P->R 与 Q->R，而 P、Q 之间没有路径。写出两个拓扑序并解释。

两个前置点都要早于 R，但彼此没有约束。

思考检查

5. 不依靠背诵，从邻接表循环说明 Kahn 为什么是 O(V+E)。

计算初始顶点工作，以及每个邻接条目被读取的次数。

答案与解答

解答 · 解答 1

移除 A 后，B 可以选择而 D 降为二；再移除 B，C 从一降为零， D 从二降为一。因此答案是 C:0, D:1, E:2, F:1，下一步只能选 C。

解答 · 解答 2

图中存在有向环。剩余两个顶点所在的子图没有源点；七个顶点的部分序列不是 原九顶点图的完整拓扑序。

解答 · 解答 3

不是。永久标记表示 v 已完成，并不代表它还在当前路径上。临时标记则表示 stack 已有 v->...->u 的路径，加入 u->v 就闭合成一个有向环。

解答 · 解答 4

P,Q,R 与 Q,P,R 都合法。两者都把 P,Q 放在 R 之前，而图没有规定 P,Q 的相对次序。

解答 · 解答 5

初始化与寻找源点需要 O(V)。计算入度时每条边读取一次；主循环中每个顶点 最多取出一次，每条出边再更新一次，共 O(V+E)。相加以后仍是 O(V+E)。