拓扑排序正确性定理
概述
拓扑排序正确性定理（Topological Sort Correctness Theorem）：对有向无环图（DAG）执行深度优先搜索（DFS），按顶点完成时间递减排序即可得到一个拓扑序。等价地，有向图存在拓扑排序当且仅当它是有向无环图。
定理陈述
形式化陈述
定理（CLRS 定理20.6）：如果有向图 是 DAG，则 TOPOLOGICAL-SORT() 产生 的一个拓扑排序。即：对 中每条有向边 ，在输出序列中 出现在 之前。
等价表述： 是 DAG 当且仅当 存在拓扑排序。
证明概要
证明思路
证明分为必要性（DAG 推出拓扑排序存在）和充分性（拓扑排序存在推出 DAG）两部分。核心是利用 DFS 的完成时间蕴含的祖先-后代关系。
必要性：DAG 推出拓扑排序存在
对 DAG 执行 DFS，得到每个顶点的完成时间 。按 递减排列顶点得到序列 。
需要证明：对 中每条边 ，有 （即 排在 前面）。
按 DFS 边分类逐一验证：
-
树边： 在 的递归搜索过程中被发现。 的 DFS-VISIT 在 的 DFS-VISIT 完成之前结束，故 ，即 。成立。
-
前向边： 是 的后代但不是通过树边到达。由括号定理， 的时间戳区间完全包含在 的时间戳区间内，故 。成立。
-
横边： 在 之前被发现和完成（因为发现 时 已经是 BLACK），故 ，即 。成立。
-
后向边：由引理20.7，DAG 中不存在后向边（后向边等价于有向回路）。无需验证。
综上，对所有边 ，都有 ， 是 的拓扑排序。
充分性：拓扑排序存在推出 DAG
反证法。假设 存在拓扑排序但 不是 DAG，即 包含有向回路 。
在拓扑排序中， 排在 前面， 排在 前面，， 排在 前面。传递可得 排在 前面，矛盾。
因此 不包含有向回路， 是 DAG。
引理20.7（辅助引理）
有向图 是 DAG 当且仅当对 执行 DFS 不产生后向边。
- 必要性：若存在后向边 ，则 是 的祖先，存在从 到 的有向路径（DFS 树边），加上 形成有向回路，与 DAG 矛盾。
- 充分性：若 有有向回路 ，设 中第一个被 DFS 发现的顶点为 ，其前驱为 。当 DFS 探索 时， 已被发现（GRAY）但未完成，故 是后向边，矛盾。
参考文献：
- CLRS 第4版，第20.4节 “Topological sort”，pp. 612-613
- Tarjan, R.E., “Depth-first search and linear graph algorithms”, SIAM J. Comput., 1972
关键推论
- DAG 判定：判断有向图是否为 DAG 等价于检查 DFS 是否产生后向边，时间 。
- 拓扑排序不唯一：一个 DAG 可能有多个拓扑排序，具体取决于 DFS 的起始顶点选择和邻接表顺序。
- Kahn 算法等价性：基于入度的 Kahn 算法与 DFS 拓扑排序产生等价的结果（都是合法的拓扑序），但 Kahn 算法天然支持回路检测。
- DAG 上的动态规划：拓扑排序为 DAG 上的动态规划提供了自然的处理顺序，保证处理每个顶点时其所有前驱都已被处理。
应用场景
在算法导论中的具体应用：
- 任务调度（Ch20）：拓扑排序确定有依赖关系的任务的执行顺序，是关键路径法（CPM）和 PERT 网络分析的基础。
- 编译依赖管理：Makefile、Cargo、npm 等构建工具使用 DAG 表示模块依赖，拓扑排序确定编译顺序。循环依赖等价于 DAG 中存在回路，会被检测并报错。
- 课程先修关系：教务系统中课程间的先修关系构成 DAG，拓扑排序给出可行的选课顺序。
- DAG 上的最短/最长路径：按拓扑序处理顶点，可在 时间内求解 DAG 上的单源最短路径和最长路径问题。