OI-wiki 拓扑排序全解：DAG 线性化、Kahn 算法与 AOE 网关键路径

OI-wiki 拓扑排序全解：DAG 线性化、Kahn 算法与 AOE 网关键路径

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

拓扑排序（Topological sorting）是图论与算法竞赛中的基础工具，用于把有向无环图（DAG）的所有节点排成一个线性序列，使得每条有向边都从前向后指向。本文以 OI-wiki 图论模块的 拓扑排序文档 为主体，完整讲解拓扑排序的定义、AOV/AOE 两种活动网络模型、Kahn 算法与 DFS 算法两种实现，并结合仓库中的 DAG 文档 展开其在环检测、DAG 上 DP、关键路径求解等场景中的应用。读完本文，你将掌握拓扑排序的完整理论脉络，并能在竞赛与工程实践中直接套用文中给出的 C++ / Python 实现。

拓扑排序：把 DAG 排成一条线

定义与排课问题

拓扑排序要解决的问题是：如何给一个有向无环图的所有节点排序。

一个直观的例子是大学每学期排课。假设有「程序设计」「算法语言」「高等数学」「离散数学」「编译技术」「普通物理」「数据结构」「数据库系统」等课程：想学「数据结构」，必须先学「离散数学」；学完「数据结构」后又获得了学习「编译技术」的前置条件，而「编译技术」还有一个更前置的课程「算法语言」。这里每门课程相当于一个顶点 $u$，课程之间的先后依赖关系就是有向边 $(u, v)$（必须先学 $u$ 再学 $v$）。教务处在逻辑关系符合的前提下排出课表，就是一次拓扑排序。

如果排课的老师打瞌睡了，规定「数据结构」需要先学「操作系统」，而「操作系统」的前置课程又是「数据结构」，那么在不考虑同时学习的情况下，到底应该先学哪一门？此时「数据结构」与「操作系统」之间形成了一个环，同学们无法确定学习的先后顺序，也就无法进行拓扑排序。只要有向图中存在环路，就无法进行拓扑排序。

因此可以给出严格定义：在一个 DAG（有向无环图） 中，将图中的顶点以线性方式进行排序，使得对于任何有向边 $(u, v)$，都有 $u$ 排在 $v$ 的前面。

依赖关系与排序目标

给定一个 DAG：

• 如果从 $i$ 到 $j$有边，则认为 $j$依赖于 $i$；
• 如果从 $i$ 到 $j$有路径（$i$ 可达 $j$），则称 $j$间接依赖于 $i$。

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖排在后面的节点。换句话说，序列中任何节点的所有前驱都必须出现在它之前。

AOV 网：顶点表示活动的网络

日常生活中，一项大工程可以看作若干个子工程的集合，子工程之间必定存在先后顺序——某些子工程必须在其他子工程完成后才能开始。用有向图表示这种关系时，子工程作为顶点、子工程之间的先后关系作为有向边，这样的有向图称为顶点活动网络（Activity On Vertex Network，AOV 网）。

AOV 网有以下要点：

• 一个 AOV 网必定是有向无环图，不能带有回路；
• 与一般 DAG 的区别在于，AOV 网把活动都表示在顶点上（上面排课例图就是一个 AOV 网）；
• 顶点表示活动，弧表示活动之间的优先关系；
• 在 AOV 网中不应出现环，这样就能找到一个顶点序列，使每个顶点代表的活动的前驱活动都排在该顶点前面——这样的序列称为拓扑序列；
• 一个 AOV 网的拓扑序列不是唯一的，由 AOV 网构造拓扑序列的过程称为拓扑排序。

两个基本概念：

• 前驱活动：有向边起点的活动称为终点的前驱活动。只有当一个活动的前驱全部完成后，这个活动才能进行；
• 后继活动：有向边终点的活动称为起点的后继活动。

构造拓扑序列的步骤

构造拓扑序列（也就是执行拓扑排序）只需要反复执行两步：

1. 从图中选择一个入度为零的点；
2. 输出该顶点，并从图中删除此顶点及其所有的出边。

重复上面两步，直到：

• 所有顶点都被输出——拓扑排序完成；
• 或者图中不存在入度为零的点——说明图是有环图，拓扑排序无法完成，陷入"死锁"。

检测 AOV 网是否带环的方式正是构造拓扑序列，看最终生成的序列是否包含所有顶点：若序列长度小于顶点总数，说明图中存在环。

AOE 网与关键路径

与 AOV 网对应的是AOE 网（Activity On Edge Network），即边表示活动的网。AOE 网是一个带权的有向无环图，其中：

• 顶点表示事件；
• 弧表示活动持续的时间。

AOE 网通常用来估算工程的完成时间。它应该是无环的，并且存在唯一入度为零的起始顶点（源点），以及唯一出度为零的完成顶点（汇点）。

AOE 网中的有些活动可以并行进行，所以完成整个工程的最短时间是从源点到汇点的最长活动路径长度。注意这里的"路径长度"是指路径上各活动的持续时间之和（即弧的权值之和），而不是路径上弧的数目。因为一项工程需要完成所有活动，所以最长的活动路径也就是关键路径，它决定了工程完成的总时间。

AOE 网的相关基本概念

• 活动：弧表示活动，弧的权值表示活动持续的时间。活动在其前驱事件（即该弧的起点）被触发后开始；
• 事件：顶点表示事件。事件在其所有前驱活动（即指向该顶点的弧）全部完成后被触发；
• 事件（顶点）$v_i$ 的最早发生时间，记为 $ve(i)$：该事件最早可能的发生时间，它决定了以该顶点开始的活动的最早发生时间。显然源点的最早发生时间为 $0$。由于事件发生需要其所有前驱活动全部完成，它等于初始点到该顶点的路径长度的最大值，递推式为： $$ve(i) = \max{ve(j) + val^j_i \mid j \in pre_i}$$ 其中 $val^j_i$ 表示 $j$ 到 $i$ 的边的权值（即活动持续时间），$pre_i$ 表示 $i$ 的所有前驱事件的集合；
• 事件（顶点）$v_i$ 的最迟发生时间，记为 $vl(i)$：在不推迟整个工期的前提下，该事件最晚能容忍的发生时间，它决定了所有以该事件结束的活动的最迟开始时间，等于事件的所有后继活动的最迟开始时间的最小值，递推式为： $$vl(i) = \min{vl(j) - val^i_j \mid j \in nxt_i}$$ 其中 $val^i_j$ 表示 $i$ 到 $j$ 的边的权值，$nxt_i$ 表示 $i$ 的所有后继事件的集合；
• 活动（弧）$(u, v)$ 的最早开始时间，记为 $e(u, v)$：等于其前驱事件的最早发生时间，即 $e(u,v) = ve(u)$；
• 活动（弧）$(u, v)$ 的最迟开始时间，记为 $l(u, v)$：在不推迟整个工期的前提下活动开始最晚能容忍的时间，等于其后继事件的最迟发生时间减去该活动的持续时间（权值），即 $l(u,v) = vl(v) - val^u_v$；
• 关键路径：AOE 网中从源点到汇点的最长路径的长度；
• 关键活动：关键路径上的活动，其特征是最早开始时间和最迟开始时间相等（即 $e(u,v) = l(u,v)$）。

递推求最早和最迟发生时间

求 $ve$ 与 $vl$ 需要按拓扑顺序进行：

• 最早发生时间 $ve$ 从前往后递推：按照拓扑序列从前向后扫描，每个事件取所有前驱路径的最大值；
• 最迟发生时间 $vl$ 从后往前递推：按照拓扑序列的逆序从后向前扫描，每个事件取所有后继约束的最小值。

递推公式即上文 AOE 网基本概念中的两个式子。换句话说，求关键路径的第一步就是先做一次拓扑排序——这正是拓扑排序在工程调度中的核心价值。

Kahn 算法

Kahn 算法是最直观、最常用的拓扑排序算法，其思想与"反复删除入度为零的顶点"完全一致。

过程

初始状态下，集合 $S$ 装着所有入度为 $0$ 的点，$L$ 是一个空列表：

1. 每次从 $S$ 中取出一个点 $u$（可以随便取）放入 $L$；
2. 将 $u$ 的所有出边 $(u, v_1), (u, v_2), (u, v_3), \cdots$ 删除；
3. 对于边 $(u, v)$，若将该边删除后点 $v$ 的入度变为 $0$，则将 $v$ 放入 $S$ 中。

不断重复以上过程，直到集合 $S$ 为空。最后检查图中是否存在任何边：如果有，说明这个图一定有环路；否则返回 $L$，$L$ 中顶点的顺序就是拓扑序列。

代码的核心是维持一个入度为 0 的顶点的集合。

伪代码

Kahn 算法的经典伪代码如下：

L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edges while S is not empty do remove a node n from S insert n into L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error (graph has at least one cycle) else return L (a topologically sorted order)

复杂度分析

假设图 $G = (V, E)$：

• 初始化入度为 $0$ 的集合 $S$ 时需要遍历整个图并检查每一条边，复杂度为 $O(E + V)$；
• 之后对集合 $S$ 的每次取出操作与每条边的删除操作，同样需要 $O(E + V)$ 的时间。

因此 Kahn 算法的总时间复杂度为 $O(E + V)$，空间复杂度为 $O(V)$（用于存储入度数组、队列与结果列表）。

C++ 实现

参考 topo.md 文档 中的 C++ 实现，使用邻接表与队列：

int n, m; vector<int> G[MAXN]; int in[MAXN]; // 存储每个结点的入度 bool toposort() { vector<int> L; queue<int> S; for (int i = 1; i <= n; i++) if (in[i] == 0) S.push(i); while (!S.empty()) { int u = S.front(); S.pop(); L.push_back(u); for (auto v : G[u]) { if (--in[v] == 0) { S.push(v); } } } if (L.size() == n) { for (auto i : L) cout << i << ' '; return true; } return false; }

实现要点：

• in[i]记录每个节点的入度，建图时对每条边(u, v)执行in[v]++即可初始化；
• 每弹出节点u，对其所有后继v执行--in[v]，模拟"删除出边"并实时判断入度是否归零；
• 最后通过L.size() == n判断是否成功：若结果序列长度等于节点总数则说明无环，返回true并输出序列；否则返回false表示图中存在环。

Python 实现

Python 版本利用collections.deque作为队列，逻辑与 C++ 完全一致：

from collections import defaultdict, deque def topo_sort(graph): lst = [] in_degree = defaultdict(int) for u in graph: for v in graph[u]: in_degree[v] += 1 s = deque([u for u in graph if in_degree[u] == 0]) while s: u = s.popleft() lst.append(u) for v in graph.get(u, []): in_degree[v] -= 1 if in_degree[v] == 0: s.append(v) return None if any(in_degree.values()) else lst

实现要点：

• in_degree用defaultdict(int)统计入度，graph.get(u, [])兼容孤立节点的邻接表为空的情况；
• 循环结束后，若仍有节点的入度不为零（any(in_degree.values())为真），说明图中存在环，返回None；否则返回拓扑序列lst。

下图是一个可用于手动验证的 13 节点 DAG，对应的 LaTeX/TikZ 源文件见 topo-example.tex，其边集为2→0, 2→3, 0→1, 0→5, 0→6, 3→5, 5→4, 6→4, 6→9, 7→6, 8→7, 9→10, 9→11, 9→12, 11→12：

对该图执行拓扑排序，一个合法的结果序列是：

2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12

读者可以逐条核对：序列中每个节点之后，都满足"所有前驱均已出现"的约束。

基于 DFS 的拓扑排序

除了 Kahn 算法，还可以用深度优先搜索完成拓扑排序，其核心思想是：在 DFS 的递归返回阶段（后序位置）记录节点，最终将记录顺序反转，即为拓扑序列。

C++ 实现

文档中的 C++ 实现使用三种节点状态来同时完成排序与环检测：

using Graph = vector<vector<int>>; // 邻接表 struct TopoSort { enum class Status : uint8_t { to_visit, visiting, visited }; const Graph& graph; const int n; vector<Status> status; vector<int> order; vector<int>::reverse_iterator it; TopoSort(const Graph& graph) : graph(graph), n(graph.size()), status(n, Status::to_visit), order(n), it(order.rbegin()) {} bool sort() { for (int i = 0; i < n; ++i) { if (status[i] == Status::to_visit && !dfs(i)) return false; } return true; } bool dfs(const int u) { status[u] = Status::visiting; for (const int v : graph[u]) { if (status[v] == Status::visiting) return false; if (status[v] == Status::to_visit && !dfs(v)) return false; } status[u] = Status::visited; *it++ = u; return true; } };

实现要点：

• Status::to_visit（未访问）、Status::visiting（正在递归栈中）、Status::visited（已完成）三种状态；
• 环检测：DFS 遍历到某个邻居时若发现它正处于visiting状态，说明存在返祖边，图中必有环，返回false；
• 记录顺序：在dfs的末尾（后序位置）将u写入order。由于使用反向迭代器it从order末尾向前填充，最终order恰好是正向的拓扑序列。

Python 实现

from enum import Enum, auto class Status(Enum): to_visit = auto() visiting = auto() visited = auto() def topo_sort(graph: list[list[int]]) -> list[int] | None: n = len(graph) status = [Status.to_visit] * n order = [] def dfs(u: int) -> bool: status[u] = Status.visiting for v in graph[u]: if status[v] == Status.visiting: return False if status[v] == Status.to_visit and not dfs(v): return False status[u] = Status.visited order.append(u) return True for i in range(n): if status[i] == Status.to_visit and not dfs(i): return None return order[::-1]

复杂度

基于 DFS 的拓扑排序：时间复杂度 $O(E + V)$，空间复杂度 $O(V)$（递归栈与状态数组）。

合理性证明

两种算法为何总是正确？可以这样归纳：考虑一个图，删掉某个入度为 $0$ 的节点之后，如果新图可以拓扑排序，那么原图一定也可以。反过来，如果原图可以拓扑排序，那么删掉该节点后新图依然可以。由于每次删除入度为 $0$ 的节点都保证了该节点在所有剩余节点之前输出，归纳下去即可得到完整的合法序列。

拓扑排序的应用

判断图中是否有环

拓扑排序天然具备环检测能力：

• Kahn 算法：若最终输出的节点数少于总节点数，则图中存在环；
• DFS 算法：若遍历过程中发现指向visiting状态节点的边（返祖边），则图中存在环。

这一特性同样体现在仓库的 DAG 判定文档 中——判定一个图是否是有向无环图，直接检验它能否完成拓扑排序即可；当然也可以对图做一遍 DFS，检查 DFS 树上是否存在连向祖先的非树边（返祖边），有则说明有环。此外，拓扑排序还可以用来判断图是否是一条链：若拓扑序列中每个节点恰好只有一个后继（除末尾节点外），则该图退化为一条链。

DAG 上的 DP：求最长（短）路

拓扑排序在算法竞赛中更常见的用途是为 DAG 上的 DP 提供遍历顺序。在一般图上，单源最长（短）路径的最优时间复杂度为 $O(nm)$（Bellman–Ford 算法）或 $O(m \log m)$（Dijkstra 算法）；但在 DAG 上，可以先拓扑排序，再按拓扑序遍历每个节点、用当前节点更新后续节点，把时间复杂度优化到 $O(n + m)$，状态转移方程为：

$$dis_v = \min(dis_v, dis_u + w_{u,v}) \quad \text{或} \quad dis_v = \max(dis_v, dis_u + w_{u,v})$$

仓库的 dag.md 给出了完整的 C++ 示例：先用toposort()得到序列L，再按L的顺序扫描，用min_dis/max_dis数组滚动更新，即可在 $O(n+m)$ 内求出 DAG 的单源最长（短）路。

求 AOE 网中的关键路径

如本文 AOE 网一节所述，拓扑排序是求关键路径的第一步：先按拓扑序从前往后递推 $ve$，再按逆拓扑序从后往前递推 $vl$，找出满足 $e(u,v) = l(u,v)$ 的关键活动，即可确定关键路径并估算工程完成的最短时间。

求字典序最大/最小的拓扑排序

当题目要求输出字典序最小或字典序最大的拓扑序列时，只需对 Kahn 算法做一处微调：将队列替换成最小堆/最大堆实现的优先队列。每次从优先队列中取出当前入度为 $0$ 且编号最小（或最大）的节点，即可保证序列在字典序意义下最优。此时总时间复杂度为：

$$O(E + V \log V)$$

习题与延伸阅读

• CF 1385E：需要通过构造拓扑排序解决的问题，适合练习"先判环、再构造"的完整流程；
• Luogu P1347：拓扑排序模板题，可直接用本文的 Kahn 算法实现提交验证。

进一步阅读：

• DAG（有向无环图）：DAG 的定义、性质、环判定与 DAG 上 DP 求最长（短）路的完整示例；
• DAG 上的 DP：以 DAG 为舞台的动态规划专题；
• DFS（深度优先搜索）：DFS 的基础知识，是理解 DFS 版拓扑排序与返祖边判环的前提。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki