拓扑排序

定义

拓扑排序(Topological Sort)是对有向无环图(DAG)顶点的一种线性排序,使得对图中每条有向边 (u, v),u 在序列中都出现在 v 之前。只有无环图才存在拓扑序,且拓扑序通常不唯一。

算法

常用两种实现:一是 Kahn 算法,反复取出入度为 0 的顶点并删除其出边,借助队列完成,可顺带检测环(若最终输出顶点数少于总数则有环);二是基于深度优先搜索,按顶点完成访问的逆序输出。两者时间复杂度均为 O(V+E)。

应用

广泛用于任务调度、编译顺序确定、软件包依赖解析(如 apt、npm)、构建系统(如 Make 的目标依赖)、课程先修关系安排,以及电子表格的公式重算顺序等。

说明

在关键路径分析中,拓扑序也是按依赖顺序做动态规划的前提。