xxx 拓扑排序算法 题目描述 给定一个有向无环图（DAG），要求对图中的所有顶点进行线性排序，使得对于图中的每一条有向边 \( u \to v \)，顶点 \( u \) 都出现在顶点 \( v \) 的前面。这种排序称为拓扑排序。拓扑排序常用于任务调度、依赖关系分析等场景。 解题过程 1. 核心思想 拓扑排序基于图的依赖关系：若存在边 \( u \to v \)，则 \( u \) 是 \( v \) 的前置条件。排序需保证所有顶点的前置条件均在其之前被处理。关键工具是顶点的 入度 （指向该顶点的边数）。 2. 算法步骤（Kahn算法） 步骤1：计算每个顶点的入度 遍历所有边，统计每个顶点的入度值。例如，对于边 \( u \to v \)，将 \( v \) 的入度加1。 步骤2：初始化队列 将所有入度为0的顶点加入队列（或栈）。这些顶点没有前置依赖，可立即处理。 步骤3：处理队列中的顶点 循环执行以下操作直到队列为空： 从队列中取出一个顶点 \( u \)，将其加入拓扑排序结果列表。 遍历 \( u \) 的所有邻接顶点 \( v \)： 将 \( v \) 的入度减1（相当于移除边 \( u \to v \)）。 若 \( v \) 的入度变为0，将 \( v \) 加入队列。 步骤4：检测环路 若结果列表中的顶点数小于图中总顶点数，说明图中存在环路（无法进行拓扑排序）。 3. 示例演示 假设有向图如下（顶点A、B、C、D，边为 A→B, A→C, B→D, C→D）： 初始入度 ：A:0, B:1, C:1, D:2 队列初始化 ：入度为0的顶点A入队。 处理过程 ： 取出A，结果列表为[ A ]。更新B入度→0（入队），C入度→0（入队）。 取出B，结果列表[ A,B ]。更新D入度→1（未到0，不入队）。 取出C，结果列表[ A,B,C ]。更新D入度→0（入队）。 取出D，结果列表[ A,B,C,D ]。 结果 ：拓扑排序为[ A,B,C,D]或[ A,C,B,D ]（多个合法顺序）。 4. 关键点说明 DAG必要性 ：拓扑排序仅适用于有向无环图。若存在环路，环路中的顶点入度永远不会减至0。 时间复杂度 ：O(V+E)，其中V为顶点数，E为边数。 应用场景 ：课程安排、编译顺序（依赖解析）、工作流调度等。 通过以上步骤，可系统性地得到DAG的拓扑排序，确保所有依赖关系被满足。