|
|
拓扑排序用于有向无环图（DAG），确保若有边 $u \to v$，则 $u$ 在 $v$ 前。用途：任务调度、课程依赖。
步骤
- 计算每个节点的入度（指向它的边数）。
- 将入度为 0 的节点加入队列。
- 从队列取节点，加入结果列表：
- 减少其邻居节点的入度。
- 若邻居入度变为 0，加入队列。
- 重复直到队列为空。
- 若结果未包含所有节点，则图有环，无法拓扑排序。
时间复杂度：$O(V + E)$，$V$ 为节点数，$E$ 为边数。
算法证明
- 初始时，入度 0 的节点无前驱，可先排序。
- 处理节点 $u$ 时，减少邻居 $v$ 的入度，模拟完成 $u$ 后解锁 $v$。
- 当 $v$ 入度为 0 时，所有前驱已处理，确保 $u$ 在 $v$ 前。
- 在 DAG 中，无环，所有节点最终入度为 0，被处理。
- 若有环，某些节点入度永不为 0，检测出环，无法排序。
示例
图：节点 0, 1, 2, 3，边 $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$
- 入度：0:0, 1:1, 2:1, 3:2
- 队列：[0]，结果：[0]
- 处理 0：1,2 入度减 1，队列：[1,2]，结果：[0,1]
- 处理 1：3 入度减 1，队列：[2]，结果：[0,1,2]
- 处理 2：3 入度变 0，队列：[3]，结果：[0,1,2,3]
- 处理 3：队列空，结束
结果：$[0,1,2,3]$ |
|
