拓扑排序 描述 拓扑排序是针对有向无环图（DAG）的顶点进行线性排序的算法，使得对于图中的任意一条有向边 \( u \to v \)，在排序中顶点 \( u \) 都出现在顶点 \( v \) 之前。拓扑排序常用于依赖关系分析，例如任务调度、编译顺序确定等场景。若图中存在环，则无法进行拓扑排序。 解题过程 理解图的结构 拓扑排序基于有向图，每个顶点代表一个任务或事件，边代表依赖关系（如 \( u \to v \) 表示 \( u \) 完成后才能进行 \( v \)）。 需确保图中无环，否则依赖关系矛盾，无法排序。 计算顶点的入度 入度指指向某顶点的边的数量。初始化时统计每个顶点的入度（例如通过遍历边列表）。 示例：对于边 \( (u, v) \)，顶点 \( v \) 的入度加 1。 初始化队列 将所有入度为 0 的顶点加入队列（这些顶点没有前置依赖，可优先处理）。 队列用于按顺序处理顶点，确保依赖关系被满足。 处理队列中的顶点 从队列中取出一个顶点 \( u \)，将其加入拓扑排序结果列表。 遍历 \( u \) 的所有邻接顶点 \( v \)（即 \( u \to v \) 的边），将 \( v \) 的入度减 1（表示依赖 \( u \) 的条件已满足）。 若 \( v \) 的入度减为 0，将 \( v \) 加入队列（表示 \( v \) 的所有前置任务已完成）。 检测环路与完成排序 若最终排序结果包含所有顶点，说明图是无环的，排序有效。 若结果中顶点数量少于图中总顶点数，说明存在环，无法完成拓扑排序。 示例 假设有向图包含边：\( A \to B \), \( A \to C \), \( B \to D \), \( C \to D \)。 步骤 1：入度统计：A(0), B(1), C(1), D(2)。 步骤 2：初始队列为 [ A ]（入度 0）。 步骤 3：处理 A，结果列表为 [ A]，更新 B 和 C 的入度（B:0, C:0），队列变为 [ B, C ]。 步骤 4：处理 B，结果列表 [ A, B]，更新 D 的入度（D:1），队列剩 [ C ]。 步骤 5：处理 C，结果列表 [ A, B, C]，更新 D 的入度（D:0），队列变为 [ D ]。 步骤 6：处理 D，结果列表 [ A, B, C, D ]。 最终拓扑排序为 A, B, C, D 或 A, C, B, D（多个合法顺序取决于队列处理顺序）。 关键点 拓扑排序的时间复杂度为 \( O(V + E) \)，其中 \( V \) 为顶点数，\( E \) 为边数。 若需所有可能排序结果，需使用回溯法枚举；若仅需一个解，队列法更高效。 实际应用中需结合具体场景（如并行任务调度）优化队列策略。