按先修关系安排顺序
很多调度问题并不要求一个数值最优解，而是要找到任意一个合法顺序。修读某门课程前要先完成所有先修课；编译某个模块前要先处理它依赖的模块；穿鞋前要先穿袜子。有些任务之间没有依赖，它们的先后次序就可以交换。
有向图恰好能够表达这种约束：顶点代表任务，边 u->v 表示 u 必须排在
v 前面。第一个任务不能有尚未完成的前置任务。如果每个剩余任务都还依赖另一个任务，就没有任何任务可以先做；沿这些依赖追溯，有限图中必然重遇某个任务，从而发现一个环。
Kahn 算法从“全部前置条件已经满足”的顶点开始向前构造；DFS 方法等到顶点完成后才将它放进答案，利用反向完成次序得到结果。两者不只是排序程序，也都能检测有向环。
实际系统往往会把输出顺序交给下一个处理阶段，因此漏掉顶点的部分序列并不是小的格式问题，而是一个无法执行的错误调度。
拓扑序与未完成的前置条件
定义 5.4.1
（有向无环图）
有向图 G=(V,E) 的每条边都是有顺序的二元组 (u,v)。如果存在
v_0->v_1->...->v_k->v_0，图中就有一个有向环。没有任何有向环的有向图称为有向无环图（directed acyclic graph，DAG）。
方向不能忽略。u->v 是从 u 指向 v 的单向约束，并不自动包含反方向。因此，无向图中的环与这里讨论的有向环不是同一个概念。
定义 5.4.2
（拓扑序）
G=(V,E) 的拓扑序是一个恰好包含每个顶点一次的序列，而且对于每条边
u->v，u 都出现在 v 之前。如果 pos(x) 表示位置，那么每条边都必须让 pos(u) 严格小于 pos(v)。
拓扑序不一定唯一。如果 x 和 y 之间不存在任一方向的可达关系，图可能没有规定它们谁先谁后。算法遇到多个同时合法的选择时，不同的 tie-breaking 会产生不同但同样正确的答案。拓扑排序寻找的是满足约束的一个顺序，而不是必然唯一的顺序。
定义 5.4.3
（入度、源点与邻接表）
indegree[v] 是进入 v 的边数；入度为零的顶点称为源点。邻接表
adj[u] 只列出所有由 u 指向的后继顶点。
两种算法都需要从已处理顶点沿出边前进，所以邻接表比每次扫描邻接矩阵的一整行更合适。图的遍历 已经区分了发现与完成；DFS 检测环时还要区分三种状态：未标记、位于当前递归路径上的临时标记，以及连同全部后继都已完成的永久标记。遇到临时标记意味着一条边返回当前路径上的祖先，从而闭合为有向环。
合法顺序何时存在
定理 5.4.4
（拓扑序存在当且仅当图是 DAG）
有向图如果包含有向环，就不存在拓扑序；反过来，每个有限 DAG 都至少有一个拓扑序。
关键结构事实是：每个非空有限 DAG 都有源点。假如每个顶点都有入边，任选一点并不断沿入边反向前进；由于顶点数有限，最终一定重复某个顶点并形成有向环。因此 DAG 必然有一个可以安全放在首位的源点；移除它后剩余图仍是 DAG，于是可以重复同一论证。
假设存在环 v_0->v_1->...->v_k->v_0。每条边都要求下一个位置严格更大，沿环走一圈就会要求 pos(v_0) 严格小于自己，产生矛盾。这不仅是说某幅图里碰巧有一支箭向左，而是任何线性排列都至少违反环上的一条边。
Kahn 不变量与正确性
定理 5.4.5
（Kahn 算法的处理数判据）
Kahn 算法输出全部 |V| 个顶点，当且仅当输入图是 DAG。如果零入度容器已空，但输出数 k 小于 |V|，未处理子图中必然存在有向环。
所以实现不能把部分序列当作成功结果；必须比较已输出数量与总顶点数。
维护不变量：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；选择只影响返回哪一个合法顺序，不影响正确性。若用 priority queue 保证每次取标签最小的可选顶点，还要计入堆操作的对数成本；普通拓扑排序并不要求这种额外次序。
DFS 标记、完成逻辑与正确性
定理 5.4.6
（反向 DFS 完成次序是拓扑序）
如果 DFS 没有遇到指向临时标记顶点的边，每个顶点完成时将它加入答案最前端，最终序列就是一个拓扑序。
这里必须使用完成时刻，而不是首次发现时刻。另一种等价写法是在完成时 push 进 stack，并在整个 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 同样只启动每个顶点一次、检查每条出边一次。用链表在常数时间内前插，或先向数组末尾追加、最后统一反转，输出操作的总成本也是线性的，因此 DFS 仍为 O(V+E)。两者在图存储之外都需要 O(V) 辅助空间。若改用邻接矩阵，每个顶点都要扫描 V
个可能邻居，即使图很稀疏也需要 O(V^2) 时间。
同一个图中的顺序与环
例题 5.4.7
（检查顺序并观察非唯一性）
考虑包含以下边的图：
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 的尾端反而更晚。检查拓扑序时必须检查所有图边，不能只看序列中的相邻顶点。
例题 5.4.8
（完整 Kahn 执行轨迹）
初始入度为 A:0, B:1, C:1, D:3, E:2, F:1。当 D,F 同时可选时，先取 F，状态如下：
| 步骤 | 取出 | 入度更新 | 随后可选 | 输出 |
|---|---|---|---|---|
| 起点 | — | — | {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；这个分支就是多个拓扑序的具体来源。
例题 5.4.9
（同一个图的完整 DFS 完成轨迹）
从 B 开始，并按照 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。加入最前的次序与完成次序相反。
例题 5.4.10
（两种方法怎样揭示同一个环）
在上述图中加入 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. 在上述图中，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)。