拓扑排序的Kahn算法 题目描述 ： 拓扑排序是针对有向无环图（DAG）的一种线性排序，使得对于图中的每一条有向边(u, v)，u在排序中都出现在v之前。Kahn算法是一种基于贪心策略的拓扑排序算法，通过不断移除入度为0的顶点来实现排序。 知识要点 ： 拓扑排序只适用于有向无环图 入度：指向某个顶点的边的数量 算法核心：维护入度为0的顶点集合 时间复杂度：O(V+E)，其中V是顶点数，E是边数 解题过程 ： 计算每个顶点的入度 初始化一个数组indegree，长度为顶点数V，所有元素初始化为0 遍历图中的所有边，对于每条边u→v，将顶点v的入度加1 示例：对于边A→B，B的入度增加1；对于边A→C，C的入度增加1 初始化队列 创建一个队列（或优先队列，如果需要特定顺序） 遍历所有顶点，将所有入度为0的顶点加入队列 这些顶点是当前没有前驱的顶点，可以立即排在结果序列中 处理队列中的顶点 从队列中取出一个顶点u，将其加入结果列表 遍历u的所有邻接顶点v（即u→v的边） 对于每个邻接顶点v，将其入度减1 如果v的入度变为0，将v加入队列 重复此过程直到队列为空 检查结果 如果结果列表中的顶点数等于图中的顶点数，说明拓扑排序成功 如果结果列表中的顶点数小于图中的顶点数，说明图中存在环，无法进行拓扑排序 算法示例 ： 考虑有向图：A→B, A→C, B→D, C→D 步骤： 计算入度：A:0, B:1, C:1, D:2 初始队列：[ A ]（只有A的入度为0） 处理A：结果=[ A]，更新B入度→0，C入度→0，队列=[ B,C ] 处理B：结果=[ A,B]，更新D入度→1，队列=[ C ] 处理C：结果=[ A,B,C]，更新D入度→0，队列=[ D ] 处理D：结果=[ A,B,C,D ] 最终拓扑排序：A→B→C→D 或 A→C→B→D 关键点 ： 队列保证了顶点的处理顺序 入度的动态更新确保了依赖关系的正确性 结果验证可以检测图中是否存在环 应用场景 ： 任务调度（有依赖关系的任务排序） 课程安排（先修课程关系） 编译顺序（源文件依赖关系） 工作流管理 Kahn算法通过简单的入度管理和队列操作，高效地解决了DAG的拓扑排序问题，是处理有依赖关系排序问题的经典算法。