拓扑排序算法 题目描述 给定一个有向无环图（DAG），要求将所有顶点排序成一个线性序列，使得对于图中的每一条有向边 \( u \to v \)，在序列中顶点 \( u \) 都出现在顶点 \( v \) 的前面。这种排序称为拓扑排序。 解题过程 理解有向无环图（DAG）的特性 ： DAG 中没有循环依赖（即不存在环），这是拓扑排序可行的前提。 拓扑排序的结果不唯一，可能存在多个有效序列。 核心思路 ： 通过不断移除“入度为 0 的顶点”（即没有前置依赖的顶点），并记录移除顺序，最终得到排序序列。 入度（In-degree）指指向某顶点的边的数量。 Kahn 算法步骤 ： 步骤 1 ：初始化。 计算每个顶点的入度，存入数组 inDegree[] 。 将所有入度为 0 的顶点加入队列（或栈）。 步骤 2 ：处理队列中的顶点。 从队列中取出一个顶点 \( u \)，将其加入拓扑序列。 遍历 \( u \) 的所有邻接顶点 \( v \)： 将 \( v \) 的入度减 1（相当于移除边 \( u \to v \)）。 如果 \( v \) 的入度变为 0，将 \( v \) 加入队列。 步骤 3 ：检查结果。 若拓扑序列包含所有顶点，则排序成功。 若序列长度小于顶点数，说明图中存在环，无法拓扑排序。 示例 （以顶点 A→B, A→C, B→D, C→D 为例）： 初始入度：A:0, B:1, C:1, D:2。 队列初始为 [ A ]，序列为空。 处理 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（取决于队列顺序）。 关键点 ： 必须确保图为 DAG（无环），否则算法会提前终止。 时间复杂度为 O(V+E)，其中 V 是顶点数，E 是边数。 通过以上步骤，可逐步得到拓扑排序，适用于任务调度、依赖关系分析等场景。