13.4.4 拓扑排序

拓扑排序用于有向无环图，也叫 DAG。它把“先后依赖关系”排成一个线性序列，使得每条有向边 u -> v 中，u 都排在 v 前面。

什么时候用拓扑排序

场景	顶点	有向边
课程学习计划	课程	先修关系
工程任务	任务	前置依赖
编译模块	文件/模块	依赖关系

如果图中有环，就不存在拓扑排序。例如 A 依赖 B，B 又依赖 A，谁也不能先完成。

算法过程

1. 统计每个顶点的入度。
2. 选择一个入度为 0 的顶点输出。
3. 删除该顶点及其发出的边。
4. 更新相关顶点入度。
5. 重复直到所有顶点输出；若中途没有入度为 0 的顶点但仍有顶点未输出，说明有环。

flowchart TD
  A["统计入度"] --> B["选入度为0的顶点"]
  B --> C["输出该顶点"]
  C --> D["删除它发出的边"]
  D --> E["更新入度"]
  E --> F{"还有顶点？"}
  F -->|有且存在入度0| B
  F -->|有但无入度0| G["存在环，排序失败"]
  F -->|无| H["得到拓扑序列"]

拓扑序列不一定唯一

如果同一时刻有多个入度为 0 的顶点，任选其一都可能得到合法拓扑序列。因此选择题常问“哪个可能是拓扑序列”，而不是唯一序列。

判断一个序列是否合法，只要检查每条边的前后顺序是否满足依赖。

与 DFS/BFS 的区别

对比项	拓扑排序	DFS/BFS
适用图	有向无环图	一般图
目标	依赖关系线性化	访问所有可达顶点
关键条件	入度为 0	邻接顶点
失败条件	图中有环	一般不存在“失败”，但非连通图需多起点

本节例题

单选

拓扑排序适用于：

A有向无环图B任意无向图C带权完全图D含自环的有向图

自查清单

1. 能否解释为什么入度为 0 的顶点可以先输出？
2. 能否判断一个给定序列是否满足所有有向边的先后关系？
3. 能否说明为什么有环时拓扑排序失败？