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 NetworkAOV 网。AOV 网有以下要点一个 AOV 网必定是有向无环图不能带有回路与一般 DAG 的区别在于AOV 网把活动都表示在顶点上上面排课例图就是一个 AOV 网顶点表示活动弧表示活动之间的优先关系在 AOV 网中不应出现环这样就能找到一个顶点序列使每个顶点代表的活动的前驱活动都排在该顶点前面——这样的序列称为拓扑序列一个 AOV 网的拓扑序列不是唯一的由 AOV 网构造拓扑序列的过程称为拓扑排序。两个基本概念前驱活动有向边起点的活动称为终点的前驱活动。只有当一个活动的前驱全部完成后这个活动才能进行后继活动有向边终点的活动称为起点的后继活动。构造拓扑序列的步骤构造拓扑序列也就是执行拓扑排序只需要反复执行两步从图中选择一个入度为零的点输出该顶点并从图中删除此顶点及其所有的出边。重复上面两步直到所有顶点都被输出——拓扑排序完成或者图中不存在入度为零的点——说明图是有环图拓扑排序无法完成陷入死锁。检测 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$ 是一个空列表每次从 $S$ 中取出一个点 $u$可以随便取放入 $L$将 $u$ 的所有出边 $(u, v_1), (u, v_2), (u, v_3), \cdots$ 删除对于边 $(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; vectorint G[MAXN]; int in[MAXN]; // 存储每个结点的入度 bool toposort() { vectorint L; queueint 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 vectorvectorint; // 邻接表 struct TopoSort { enum class Status : uint8_t { to_visit, visiting, visited }; const Graph graph; const int n; vectorStatus status; vectorint order; vectorint::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(nm)$ 内求出 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
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 NetworkAOV 网。AOV 网有以下要点一个 AOV 网必定是有向无环图不能带有回路与一般 DAG 的区别在于AOV 网把活动都表示在顶点上上面排课例图就是一个 AOV 网顶点表示活动弧表示活动之间的优先关系在 AOV 网中不应出现环这样就能找到一个顶点序列使每个顶点代表的活动的前驱活动都排在该顶点前面——这样的序列称为拓扑序列一个 AOV 网的拓扑序列不是唯一的由 AOV 网构造拓扑序列的过程称为拓扑排序。两个基本概念前驱活动有向边起点的活动称为终点的前驱活动。只有当一个活动的前驱全部完成后这个活动才能进行后继活动有向边终点的活动称为起点的后继活动。构造拓扑序列的步骤构造拓扑序列也就是执行拓扑排序只需要反复执行两步从图中选择一个入度为零的点输出该顶点并从图中删除此顶点及其所有的出边。重复上面两步直到所有顶点都被输出——拓扑排序完成或者图中不存在入度为零的点——说明图是有环图拓扑排序无法完成陷入死锁。检测 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$ 是一个空列表每次从 $S$ 中取出一个点 $u$可以随便取放入 $L$将 $u$ 的所有出边 $(u, v_1), (u, v_2), (u, v_3), \cdots$ 删除对于边 $(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; vectorint G[MAXN]; int in[MAXN]; // 存储每个结点的入度 bool toposort() { vectorint L; queueint 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 vectorvectorint; // 邻接表 struct TopoSort { enum class Status : uint8_t { to_visit, visiting, visited }; const Graph graph; const int n; vectorStatus status; vectorint order; vectorint::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(nm)$ 内求出 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
