拓扑排序的应用

定义

拓扑排序是对有向无环图（DAG）的所有顶点排成一个线性序列，使得图中任意一条边 $\langle u,v\rangle$，$u$ 在序列中都出现在 $v$ 之前。

算法步骤（Kahn 算法 / 入度表法）

1. 计算所有顶点的入度
2. 将所有入度为 0 的顶点入队（或栈）
3. 循环：
   a. 取出一个入度为 0 的顶点 v，加入结果序列
   b. 删除 v 的所有出边（即 v 的每个邻接点入度减 1）
   c. 若某邻接点入度变为 0，入队
4. 若结果序列包含所有顶点 → 排序成功
   若结果序列顶点数 < 总顶点数 → 图中有环

DFS 实现思路

对每个未访问顶点进行 DFS：
1. 先递归访问所有后继
2. 当前顶点访问完毕后入栈
3. 最终栈的逆序即为拓扑排序
（后序遍历的逆序 = 拓扑排序）

例题 1：基础拓扑排序

顶点 A~F，边 A→C, A→D, B→D, B→E, C→F, D→F, E→F。

拓扑排序结果：A, B, C, D, E, F（不唯一，取决于入队顺序）。

例题 2：检测环

边 A→B, B→C, C→A, C→D。所有顶点入度均为 1，没有任何入度为 0 的顶点，无法开始 ⟹ 图中有环（A→B→C→A）。

例题 3：课程安排问题

先修关系：C3 需先修 C1；C4 需先修 C1、C2；C5 需先修 C3、C4；C6 需先修 C5。

等价 DAG：C1→C3, C1→C4, C2→C4, C3→C5, C4→C5, C5→C6。

入度：$C1=0, C2=0, C3=1, C4=2, C5=2, C6=1$。一种合法选课顺序：C1 → C2 → C3 → C4 → C5 → C6。

例题 4：关键路径中的应用

1. 拓扑排序确定事件最早发生时间 $ve$（正向遍历）
2. 逆拓扑序确定事件最迟发生时间 $vl$（逆向遍历）
3. 关键活动：$e(i) = l(i)$ 的活动