拓扑排序的Kahn算法 拓扑排序用于对有向无环图（DAG）的节点进行线性排序，使得对于任何有向边 \( u \to v \)，节点 \( u \) 都排在节点 \( v \) 之前。Kahn算法是一种基于贪心策略的广度优先方法，其核心思想是不断选择入度为0的节点，并移除其出边，直到所有节点被处理或发现图中存在环。 算法步骤详解 初始化入度表 遍历图中所有节点，统计每个节点的入度（即指向该节点的边数），并记录每个节点的出边（邻接表）。 构建初始队列 将所有入度为0的节点加入队列（或栈/列表）。这些节点没有前置依赖，可以直接作为拓扑排序的起点。 处理节点并更新入度 从队列中取出一个节点，将其加入拓扑排序的结果列表。 遍历该节点的所有邻接节点（即出边指向的节点），将它们的入度减1（相当于移除当前节点及其出边）。 若某个邻接节点的入度减至0，则将其加入队列。 检测环与终止条件 若结果列表中的节点数等于总节点数，说明拓扑排序成功，返回结果。 若队列为空但结果列表中的节点数少于总节点数，说明图中存在环，无法进行拓扑排序。 举例说明 假设有向图包含边：\( A \to B, A \to C, B \to D, C \to D \)。 初始化入度表 ： 入度：\( A:0, B:1, C:1, D:2 \) 邻接表：\( A:[ B,C], B:[ D], C:[ D], D:[ ] \) 初始队列 ：入度为0的节点 \( A \) 入队。 循环处理 ： 取出 \( A \)，加入结果列表。更新邻接节点 \( B \) 和 \( C \) 的入度（分别减1），此时 \( B:0, C:0 \)。将 \( B, C \) 入队。 取出 \( B \)，加入结果。更新 \( D \) 的入度（减1），此时 \( D:1 \)。 取出 \( C \)，加入结果。更新 \( D \) 的入度（减1），此时 \( D:0 \)，将 \( D \) 入队。 取出 \( D \)，加入结果。 结果 ：拓扑排序为 \( [ A, B, C, D] \)（或 \( [ A, C, B, D ] \)，取决于队列顺序）。 关键点与复杂度 时间复杂度 ：\( O(V+E) \)，其中 \( V \) 为节点数，\( E \) 为边数。每个节点和边仅被处理一次。 空间复杂度 ：\( O(V) \)（存储入度表、队列、邻接表）。 应用场景 ：任务调度、依赖解析（如编译器的模块加载）、课程安排等。 对比DFS方法 Kahn算法显式利用入度信息，易于理解且无需递归栈；而基于DFS的拓扑排序需要通过递归深度标记判断环，但能更灵活地结合其他图遍历需求。