xxx 有向无环图（DAG）中的拓扑排序算法
字数 1217 2025-11-18 01:58:16
xxx 有向无环图（DAG）中的拓扑排序算法
问题描述
给定一个有向无环图（DAG），要求输出一个顶点的线性序列，使得对于图中任意一条有向边 \(u \to v\)，在序列中顶点 \(u\) 都出现在顶点 \(v\) 的前面。这种序列称为拓扑排序（Topological Sorting）。拓扑排序常用于任务调度、依赖关系分析等场景。
解题过程
1. 理解拓扑排序的核心性质
- 有向无环图（DAG）：图中不存在任何环，否则拓扑排序无法进行。
- 偏序关系：边 \(u \to v\) 表示 \(u\) 必须先于 \(v\) 出现，但不相连的顶点间顺序任意。
- 入度（In-Degree）：指向某顶点的边的数量。拓扑排序通常从入度为 0 的顶点开始。
2. 算法选择：Kahn 算法（基于 BFS）
Kahn 算法通过维护入度为 0 的顶点集合，逐步移除顶点并更新相邻顶点的入度，最终得到拓扑序列。
步骤详解：
-
初始化：
- 计算每个顶点的入度，存入数组
indegree[]。 - 将所有入度为 0 的顶点加入队列（或栈）。
- 计算每个顶点的入度，存入数组
-
处理顶点：
- 从队列中取出一个顶点 \(u\)，将其加入拓扑序列。
- 遍历 \(u\) 的所有邻接顶点 \(v\)：
- 将 \(v\) 的入度减 1。
- 若 \(v\) 的入度变为 0，将 \(v\) 加入队列。
- 重复直到队列为空。
-
检测环：
- 若拓扑序列长度不等于顶点总数，说明图中存在环，无法进行拓扑排序。
3. 示例演示
考虑以下 DAG（顶点 0~4，边为 0→1, 0→2, 1→3, 2→3, 3→4）：
0 → 1 → 3 → 4
↘ 2 ↗
逐步执行：
- 初始入度：
[0,1,1,2,1]（顶点 0 入度为 0，其他顶点入度非零）。 - 队列初始化为
[0]。 - 取出 0：
- 序列：
[0] - 更新 1 的入度→0，2 的入度→0，队列变为
[1,2]。
- 序列：
- 取出 1：
- 序列：
[0,1] - 更新 3 的入度→1，队列为
[2]。
- 序列：
- 取出 2：
- 序列：
[0,1,2] - 更新 3 的入度→0，队列为
[3]。
- 序列：
- 取出 3：
- 序列：
[0,1,2,3] - 更新 4 的入度→0，队列为
[4]。
- 序列：
- 取出 4：
- 序列：
[0,1,2,3,4]（完成）。
- 序列：
4. 关键细节
- 时间复杂度：\(O(V+E)\)，其中 \(V\) 为顶点数，\(E\) 为边数。
- 空间复杂度：\(O(V)\)（存储入度和队列）。
- 多解情况：当队列中存在多个入度为 0 的顶点时，任意选择顺序均合法（例如示例中 1 和 2 可互换）。
- 环检测：若最终序列长度不足 \(V\)，说明剩余顶点均存在环依赖。
5. 应用场景
- 课程安排：前置课程必须在后续课程之前完成。
- 编译顺序：源文件间的依赖关系。
- 工作流调度：任务间的先后约束。
通过以上步骤，可以系统地求解任何 DAG 的拓扑排序，并确保依赖关系的正确性。