图的拓扑排序算法 题目描述 拓扑排序是针对有向无环图（DAG）的顶点进行线性排序的算法，使得对于图中的任意有向边 \( u \to v \)，在排序中顶点 \( u \) 都出现在顶点 \( v \) 的前面。拓扑排序常用于任务调度、依赖关系分析等场景。若图中存在环，则无法进行拓扑排序。 解题过程 拓扑排序有两种经典实现： Kahn算法 （基于入度）和 DFS深度优先搜索算法 。下面逐步讲解两种方法。 方法一：Kahn算法（基于入度） 核心思想 ：不断选择入度为0的顶点，移除该顶点及其出边，更新相邻顶点的入度，重复直到所有顶点被处理。 步骤详解 ： 初始化 ： 计算每个顶点的入度（即指向该顶点的边数）。 使用队列（或栈）存储当前所有入度为0的顶点。 循环处理 ： 从队列中取出一个入度为0的顶点 \( u \)，将其加入拓扑排序结果列表。 遍历 \( u \) 的所有邻接顶点 \( v \)： 将 \( v \) 的入度减1（相当于移除边 \( u \to v \)）。 若 \( v \) 的入度变为0，将 \( v \) 加入队列。 重复直到队列为空。 检测环 ： 若结果列表中的顶点数小于图的总顶点数，说明图中存在环，无法完成拓扑排序。 示例 （图：边集合为 [(1,2), (1,3), (2,4), (3,4)] ）： 初始入度：1:0, 2:1, 3:1, 4:2。 队列初始化为 [1] （入度为0的顶点）。 处理1：结果列表 [1] ，更新顶点2、3的入度（变为0），队列变为 [2,3] 。 处理2：结果列表 [1,2] ，更新顶点4的入度（变为1），队列变为 [3] 。 处理3：结果列表 [1,2,3] ，更新顶点4的入度（变为0），队列变为 [4] 。 处理4：结果列表 [1,2,3,4] 。 最终排序为 [1,2,3,4] 或 [1,3,2,4] （多个合法顺序）。 方法二：DFS深度优先搜索 核心思想 ：通过DFS遍历顶点，在顶点完成遍历时（即回溯阶段）将其加入结果列表，最终反转结果得到拓扑排序。 步骤详解 ： 初始化 ： 标记所有顶点为未访问状态。 使用栈（或递归）记录DFS路径，同时需检测环。 DFS遍历 ： 对每个未访问的顶点执行DFS： 标记顶点为访问中（临时状态，用于环检测）。 递归访问其所有未完成的邻接顶点。 若遇到访问中的顶点，说明存在环，直接返回错误。 标记顶点为已完成，将其加入结果列表。 反转结果 ： DFS完成后，按逆序输出结果列表（或直接使用栈存储，最后出栈即为正序）。 示例 （同上图）： 从顶点1开始DFS：访问1 → 访问2 → 访问4（无邻接点，加入结果） → 回溯加入2 → 访问3 → 访问4（已访问，跳过） → 回溯加入3 → 回溯加入1。 结果列表为 [4,2,3,1] ，反转后得到 [1,3,2,4] 。 比较与适用场景 ： Kahn算法 ：直观易实现，适合动态检测环，常用于任务调度系统。 DFS算法 ：适合需要深度遍历的场景，可同时检测环，但递归深度可能受栈限制。 时间复杂度 ：两种方法均为 \(O(V+E)\)（顶点数+边数）。 空间复杂度 ：\(O(V)\)（存储入度或DFS栈）。 通过以上步骤，可灵活应用拓扑排序解决依赖关系问题。