拓扑排序Topological Sort和关键路径Critical Path Method, CPM是图论与项目管理中密切相关的两个重要概念均基于有向无环图DAG且在数据结构中常依托邻接表/邻接矩阵、入度数组、栈/队列及**优先队列用于关键路径中的最早/最晚时间计算**等实现。拓扑排序适用对象有向无环图DAG反映任务间的偏序关系如课程先修、编译依赖。核心思想按顶点的“依赖顺序”线性排列使得每条有向边 (u → v) 中 u 总在 v 之前出现。常用算法Kahn 算法基于入度的 BFS或 DFS记录逆后序。数据结构支撑邻接表存储图入度数组indegree[]跟踪各顶点入度队列Kahn或递归栈DFS维护待处理节点。关键路径应用场景AOE网Activity On Edge network即带权有向无环图边表示活动、权值为持续时间顶点表示事件里程碑。目标找出从源点到汇点的最长路径因决定整个工程最短完成时间该路径上的活动为“关键活动”无浮动时间。计算步骤拓扑排序确保事件处理顺序正向遍历求各事件的最早发生时间 ve[i]最长路径长度逆向遍历需逆邻接表或反向图求各事件的最晚发生时间 vl[i]对每条边 ⟨i, j⟩ 权值 w若 ve[i] vl[j] − w则该活动为关键活动。数据结构需求邻接表 逆邻接表或存储反向边ve[]、vl[] 数组辅助栈/队列用于拓扑序列存储与逆序访问。二者关系拓扑排序是求解关键路径的前提和基础——只有在 DAG 上完成拓扑排序才能保证 ve/vl 的动态规划式计算满足依赖顺序。# Kahn拓扑排序示例邻接表 入度fromcollectionsimportdequedeftopological_sort(graph,n):indegree[0]*nforuinrange(n):forvingraph[u]:indegree[v]1qdeque([iforiinrange(n)ifindegree[i]0])topo_order[]whileq:uq.popleft()topo_order.append(u)forvingraph[u]:indegree[v]-1ifindegree[v]0:q.append(v)returntopo_orderiflen(topo_order)nelse[]# 有环则返回空利用拓扑排序结果在线性时间内计算 AOE 网中各事件的最早发生时间 ve[i]核心思想是按拓扑序正向递推每个事件的 ve 值等于其所有前驱事件的 ve 对应活动边权值的最大值。由于拓扑序保证了“所有前驱已处理”因此每条边仅被访问一次总时间复杂度为O(V E)即线性。✅ 具体步骤如下前提准备已知 AOE 网的邻接表graphgraph[u] [(v, w)]表示从事件 u 到事件 v 的活动耗时 w已通过 Kahn 或 DFS 得到合法拓扑序列topo_order长度为 n索引 0 → n−1 为执行顺序初始化ve[0..n−1] 0源点 ve[0] 通常设为 0其余初始为 0后续更新。正向遍历拓扑序列对每个事件u按 topo_order 顺序遍历其所有出边u → v执行松弛更新ve[v]max(ve[v],ve[u]w)正确性保障拓扑序中u出现在v之前 ⇔ 所有指向v的边(u→v)的起点u都已被处理因此ve[v]在访问到v之前已由所有前驱充分更新无需重复迭代区别于 Bellman-Ford。 示例伪代码ve[0]*n# 初始化所有事件最早时间foruintopo_order:# 按拓扑序处理每个事件forv,wingraph[u]:# 遍历 u 发出的所有活动ifve[v]ve[u]w:# 松弛更早完成 v 的可能ve[v]ve[u]w⚠️ 注意事项源点入度为 0 的唯一起点的ve[source] 0若存在多个源点需显式设其ve 0若图不连通或存在不可达事件其ve保持 0可预先初始化为-∞并设源点为 0但 AOE 网通常规定单源连通 DAG此过程天然规避环检测——若拓扑排序失败返回空则 ve 计算无意义AOE 网定义要求无环。综上该方法严格依赖拓扑序的偏序性质是动态规划在 DAG 上的典型线性应用。