拓扑排序 拓扑排序是一种针对有向无环图（DAG）的线性排序算法。该排序满足：对于图中的每一条有向边 \( u \to v \)（从节点 \( u \) 指向节点 \( v \)），在排序结果中 \( u \) 都出现在 \( v \) 之前。拓扑排序常被用于解决具有依赖关系的问题，例如任务调度、课程安排等。 核心概念 有向无环图（DAG） ：拓扑排序仅适用于有向图，且图中不能存在环。如果图中存在环，则无法进行拓扑排序，因为环上的节点相互依赖，无法确定先后顺序。 入度（In-degree） ：指向某个节点的边的数量称为该节点的入度。例如，如果存在边 \( A \to B \)，则节点 \( B \) 的入度增加 1。 出度（Out-degree） ：从某个节点指出的边的数量称为该节点的出度。 算法步骤（Kahn 算法） Kahn 算法是一种基于入度的拓扑排序算法，其核心思想是不断选择入度为 0 的节点，移除该节点及其出边，并更新相邻节点的入度。具体步骤如下： 初始化 ： 计算图中每个节点的入度，并记录。 初始化一个队列（或栈），用于存储所有当前入度为 0 的节点。 初始化一个列表，用于存储拓扑排序的结果。 处理入度为 0 的节点 ： 将队列中所有入度为 0 的节点依次出队，并加入结果列表。 对于每个出队的节点 \( u \)，遍历其所有邻接节点 \( v \)（即存在边 \( u \to v \)），将 \( v \) 的入度减 1。如果减 1 后 \( v \) 的入度变为 0，则将 \( v \) 加入队列。 检查环的存在 ： 如果结果列表中的节点数量等于图中节点的总数，说明拓扑排序成功。 如果结果列表中的节点数量小于图中节点的总数，说明图中存在环，无法进行拓扑排序。 示例演示 假设有一个有向图，节点为 \( A, B, C, D, E \)，边为： \( A \to B \) \( A \to C \) \( B \to D \) \( C \to D \) \( D \to E \) 步骤 1：初始化 计算每个节点的入度： \( A: 0 \) \( B: 1 \)（来自 \( A \)） \( C: 1 \)（来自 \( A \)） \( D: 2 \)（来自 \( B \) 和 \( C \)） \( E: 1 \)（来自 \( D \)） 队列初始化为 \( [ A ] \)（因为只有 \( A \) 的入度为 0）。 结果列表初始为空。 步骤 2：处理节点 出队 \( A \)，加入结果列表：结果 = \( [ A ] \)。 更新 \( A \) 的邻接节点 \( B \) 和 \( C \)： \( B \) 的入度减 1，变为 0，将 \( B \) 加入队列。 \( C \) 的入度减 1，变为 0，将 \( C \) 加入队列。 队列变为 \( [ B, C ] \)。 出队 \( B \)，加入结果列表：结果 = \( [ A, B ] \)。 更新 \( B \) 的邻接节点 \( D \)： \( D \) 的入度减 1，变为 1（原为 2，减去 \( B \) 的边）。 队列剩余 \( [ C ] \)。 出队 \( C \)，加入结果列表：结果 = \( [ A, B, C ] \)。 更新 \( C \) 的邻接节点 \( D \)： \( D \) 的入度减 1，变为 0，将 \( D \) 加入队列。 队列变为 \( [ D ] \)。 出队 \( D \)，加入结果列表：结果 = \( [ A, B, C, D ] \)。 更新 \( D \) 的邻接节点 \( E \)： \( E \) 的入度减 1，变为 0，将 \( E \) 加入队列。 队列变为 \( [ E ] \)。 出队 \( E \)，加入结果列表：结果 = \( [ A, B, C, D, E ] \)。 步骤 3：检查结果 结果列表包含 5 个节点，与图中节点总数一致，说明拓扑排序成功。排序结果为 \( A \to B \to C \to D \to E \)（注意：\( B \) 和 \( C \) 的顺序可以互换，因为它们之间没有依赖关系）。 时间复杂度与空间复杂度 时间复杂度 ：\( O(V + E) \)，其中 \( V \) 是节点数，\( E \) 是边数。每个节点和边仅被处理一次。 空间复杂度 ：\( O(V) \)，用于存储入度数组、队列和结果列表。 应用场景 拓扑排序常用于解决依赖关系问题，例如： 课程安排：必须先修完某些课程才能修读后续课程。 任务调度：某些任务必须在其他任务之前完成。 编译顺序：模块编译的依赖关系。 通过以上步骤，可以系统地理解拓扑排序的原理和实现方法。如果图中存在环，算法会提前终止，从而检测到环的存在。