拓扑排序
拓扑排序（Topological Sort）
一项大的工程常被分为多个小的子工程，子工程之间可能存在一定的先后顺序，即某些子工程必须在其它的一些子工程完成后才能开始。在现代化管理中，有向图可以用来描述和分析一项工程的计划和实施过程，其中图的顶点表示活动，有向边表示活动之间的先后关系，这样的图称为AOV（Activity on Vertex）网。
如果图中从顶点V到W有一条有向路径，则V一定排在W之前，满足此条件的顶点序列称为一个拓扑序。AOV网如果有合理的拓扑序，则必定是有向无环图（DAG, Directed Acyclic Graph）。
可以使用卡恩Kahn算法完成拓扑排序。假设列表用于存放拓扑排序的结果，把所有入度为0的顶点放入L中，然后把这些顶点从图中去掉。重复该操作，直到找不到入度为0的顶点。如果此时L中的元素个数和图的顶点总数相同，说明拓扑排序完成；如果此时L中的元素个数少于图的顶点总数，说明原图中存在环，无法进行拓扑排序。
例如对计算机专业课安排学习顺序：
| 课程代码 | 课程名称 | 预修课程 |
|---|---|---|
| C1 | 程序设计基础 | 无 |
| C2 | 离散数学 | 无 |
| C3 | 数据结构 | C1、C2 |
| C4 | 微积分（一） | 无 |
| C5 | 微积分（二） | C4 |
| C6 | 线性代数 | C5 |
| C7 | 算法分析与设计 | C3 |
| C8 | 逻辑与计算机设计基础 | 无 |
| C9 | 计算机组成 | C8 |
| C10 | 操作系统 | C7、C9 |
| C11 | 编译原理 | C7、C9 |
| C12 | 数据库 | C7 |
| C13 | 计算理论 | C2 |
| C14 | 计算机网络 | C10 |
| C15 | 数值分析 | C6 |
互动实验
课程安排：只移除入度为0的课程
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
| 学期 | 课程 |
|---|---|
| 第一学期 | C1、C2、C4、C8 |
| 学期 | 课程 |
|---|---|
| 第一学期 | C1、C2、C4、C8 |
| 第二学期 | C3、C5、C9、C13 |
| 学期 | 课程 |
|---|---|
| 第一学期 | C1、C2、C4、C8 |
| 第二学期 | C3、C5、C9、C13 |
| 第三学期 | C6、C7 |
| 学期 | 课程 |
|---|---|
| 第一学期 | C1、C2、C4、C8 |
| 第二学期 | C3、C5、C9、C13 |
| 第三学期 | C6、C7 |
| 第四学期 | C10、C11、C12、C15 |
| 学期 | 课程 |
|---|---|
| 第一学期 | C1、C2、C4、C8 |
| 第二学期 | C3、C5、C9、C13 |
| 第三学期 | C6、C7 |
| 第四学期 | C10、C11、C12、C15 |
| 第五学期 | C14 |
互动实验
拓扑排序：发现并修复环
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
知识测验
题目
拓扑排序中，一个顶点何时可以从剩余图中移除？
知识测验
题目
还剩4个顶点，但没有任何入度0的顶点，说明什么？
动手练习
排定任务顺序并检查回路
按图中的依赖安排任务，每轮可同时完成当前所有入度0的顶点。写出各轮任务与一个合法拓扑序。再添加F→B，判断能否完成，并画出阻塞的有向环。