拓扑排序（Topological Sorting） 拓扑排序是针对 有向无环图（DAG） 的顶点进行线性排序的算法，使得对于图中的任意一条有向边 \(u \to v\)，在排序中顶点 \(u\) 都出现在顶点 \(v\) 之前。拓扑排序常用于解决任务调度、依赖关系分析等问题。 1. 拓扑排序的适用条件 图必须是有向图 ：因为依赖关系具有方向性。 图必须无环 ：如果存在环，则依赖关系形成循环，无法进行拓扑排序（例如任务A依赖任务B，任务B又依赖任务A，无法确定执行顺序）。 2. 拓扑排序的两种经典实现方法 方法一：Kahn算法（基于入度） 核心思想 ：不断选择入度为0的顶点，将其加入结果序列，并移除其所有出边，更新相邻顶点的入度。 步骤详解 ： 初始化 ： 计算每个顶点的入度（即指向该顶点的边的数量）。 将入度为0的顶点加入队列（或栈）。 循环处理 ： 从队列中取出一个顶点 \(u\)，将其加入拓扑排序结果。 遍历 \(u\) 的所有邻接顶点 \(v\)，将 \(v\) 的入度减1（相当于移除边 \(u \to v\)）。 如果减1后 \(v\) 的入度变为0，将 \(v\) 加入队列。 终止检查 ： 如果结果序列包含所有顶点，则排序成功。 如果结果序列的顶点数少于总顶点数，说明图中存在环，无法完成拓扑排序。 示例 （以图 A→B→C 和 A→C 为例）： 初始入度：A:0, B:1, C:2 队列初始值：[ A ] 处理A：结果=[ A ]，更新B入度→0（加入队列），C入度→1 处理B：结果=[ A,B ]，更新C入度→0（加入队列） 处理C：结果=[ A,B,C ] 最终拓扑排序：A→B→C 或 A→C→B（可能有多解） 方法二：深度优先搜索（DFS） 核心思想 ：通过DFS递归遍历顶点，在顶点完成所有后继节点的访问后，将其加入结果序列（逆序）。 步骤详解 ： 标记状态 ： 为每个顶点定义状态：未访问（0）、访问中（1）、已访问（2）。 使用栈或直接逆序记录结果。 DFS遍历 ： 从任意未访问顶点开始DFS。 访问顶点时标记为“访问中”，然后递归访问其所有未访问邻接顶点。 如果遇到“访问中”的顶点，说明存在环，立即终止。 当顶点的所有邻接顶点均访问完成后，标记为“已访问”，并将其加入结果序列。 逆序输出 ： DFS完成后，将结果序列反转（或直接使用栈），得到拓扑排序。 示例 （同上图）： 从A开始DFS：访问B→访问C→C完成→B完成→A完成，栈中顺序[ C,B,A ] 反转栈得到拓扑排序：[ A,B,C ] 3. 时间复杂度与空间复杂度 时间复杂度 ：两种方法均为 \(O(V+E)\)，其中V为顶点数，E为边数。 空间复杂度 ：\(O(V)\)（存储入度数组、队列/栈、状态标记等）。 4. 拓扑排序的应用场景 任务调度 ：如编译器的源文件编译顺序（依赖关系）。 课程安排 ：选修课程的前置条件判断。 软件包管理 ：解决依赖安装顺序问题。 5. 关键注意事项 拓扑排序 不唯一 ：DAG可能存在多种合法的排序结果。 检测环的重要性：在实际应用中需先确保图无环（例如Kahn算法中若剩余顶点入度均不为0，则存在环）。 通过以上步骤，可以系统地理解拓扑排序的原理与实现，并灵活应用于依赖关系分析问题。