拓扑排序

一、拓扑排序的使用场景

拓扑排序主要是用于在一个DAG（有向无环图）中将所有的顶点按照依赖顺序关系构造成一个线性序列。

• 有依赖关系的源文件编译顺序确定；
• 穿衣服的顺序确定；
• 存在先修课和后修课依赖关系时，课程顺序的安排；

拓扑排序后的线性序列不止有一种情况适合问题的解，即存在多解的情况。

二、拓扑排序及其适用范围

排序算法都是作用做特定的数据结构上的，分析以上的问题，我们发现，这些问题都可以抽象为一个有向无环图。那么问题就转化成了，如何在一个有向无环图上实现拓扑排序。

2.1 Kahn算法

• 如果p先于n执行，那么就表示为p指向n；
• 为所有顶点都初始化如上这种依赖关系，最终形成一个有向无环图（如何判断无环下面会说到）；
• 找到入度为0的顶点，该顶点表示没有其它任何步骤先于它执行；
• 将如上入度为0的顶点从图中删除，并记录到序列中，同时循环执行上一个步骤；
• 直至所有顶点都记录到序列中，那么该序列就是一个拓扑排序后的序列；

2.2 DFS算法

即深度优先搜索遍历算法，这个在讲图这种数据结构的时候有详细地说过，此处不再赘述。只不过DFS输出的序列正好也是符合拓扑排序的，因此也可以作为拓扑排序的一种解法。

2.3 适用范围

凡是需要通过局部顺序来推导全局顺序的，一般都可以使用拓扑排序来解决。但是要求，图中不能有环，否则就不能使用。那么如何判断图中是否有环呢。

如果我们使用Kahn算法，如果最后输出序列中的顶点个数，少于实际图中的个数，则说明图中还剩下入度不是0的顶点，从而说明了图中存在环。