拓扑排序Topological sort

为有向无环图生成满足依赖方向的线性顺序。

拓扑序 A、B、C、D 与 A、C、B、D 都合法。只要求每条有向边的起点排在终点之前；有环时不存在拓扑序。

时间与空间#

V 为顶点数，E 为有向边数。

邻接表上的入度队列法或 DFS 逆后序法；必须检测有向环。只有 DAG 存在拓扑顺序，合法顺序通常不唯一；优先队列选最小编号会增加对数因子。

1 个案例 · 附源码

Git·Revision walk / topo orderv2.46.0

Git 的拓扑历史遍历记录尚未输出的子提交数量；只有相关子提交都已处理，父提交才进入可输出集合。

附源码片段 · 图处理与编译

基础原理参考资料

Princeton · TopologicalDFS 排序、环检测及 DAG 条件。

Princeton · TopologicalX基于入度和队列的非递归实现。