拓扑排序
复习
- 深度优先搜索：沿一条路走到底
- 连通分量与环：检测依赖是否成环
- 图：有向图表示单向关系
TL;DR
- 拓扑排序给有依赖的任务排出可行顺序
- 它要求图是有向无环图
- 常用做法：不断取出入度为 0 的节点
- 如果存在环，就不存在拓扑排序
正文
现实里常有这样的问题：几件事之间有先后依赖，必须先做某些，才能做另一些。比如课程有先修要求、软件模块有编译依赖。怎样排出一个合法、可行的顺序？ 这就是拓扑排序（topological sort）。
用有向图表示依赖
先把依赖画成有向图：A → B 表示“A 必须在 B 之前完成”。
如果这个依赖图里有环，那就无解——A 等 B、B 又等 A，谁也开不了头。所以拓扑排序的前提是：图必须是有向无环图（DAG，Directed Acyclic Graph）。这也正好用上了上一章的“找环”。
不断拿走“没有前置”的任务
一个很直观的算法（常称为 Kahn 算法）是：
- 找出所有入度为 0 的节点——也就是没有任何前置任务、可以立刻开始的那些
- 取出一个，放进结果序列
- 把它指向的所有边删掉，相当于“这件事做完了，它后面的依赖减一”
- 如果有节点因此变成了入度 0，就加入候选
- 重复，直到所有节点都被取出
如果最后还有节点取不出来（入度始终不为 0），那说明图里有环，不存在合法顺序。顺序排不出来这件事本身，就是一个有用的信号。
它有什么用
拓扑排序的用处很实在：
- 课程安排：保证先修课排在前面
- 构建系统：按依赖顺序编译
- 任务调度：处理好各种前后关系
它也可以借助 DFS 实现：在做深度优先搜索时，节点“完成访问”的顺序反过来，就是一个拓扑序。两种实现，殊途同归。
到这里，关于“图怎么表示、怎么遍历”的内容就齐了。接下来，我们要回答图里更实际的问题：从 A 到 B，哪条路最好？
思考题 1
为什么拓扑排序要求图是有向无环图？
思考题 2
“不断取出入度为 0 的节点”，为什么能得到一个合法的顺序？
小结
知识点
- 拓扑排序为有依赖的任务排出可行顺序
- 前提是图必须是有向无环图
- Kahn 算法不断取出入度为 0 的节点
- 若最终仍有节点无法取出，说明存在环
参考资料
- Wikipedia(zh)：拓扑排序：为有向无环图排出线性顺序
- Wikipedia(zh)：有向无环图：不含环的有向图
思考题答案（仅供参考）
思考题 1
因为有环意味着存在“互相依赖、彼此等待”的关系，比如 A 依赖 B、B 又依赖 A，任何顺序都无法满足全部先后要求。只有无环，才可能排出一个所有依赖都被满足的顺序。
思考题 2
入度为 0 表示该节点没有任何尚未完成的前置任务，可以立刻执行。取出它并删除其出边后，后面的依赖相应减少；如此反复，每一步取出的节点都是“当前可以开始”的，因此得到的顺序天然满足所有依赖关系。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪