拓扑排序

拓扑排序应该是定义在图上的一种排序方式，但是其应用和可以做的事情又不仅仅限于排序

例子

比如说，编译器编译包，如果 A 包依赖于 B 包，那么需要先编译 B 包在编译 A 包，而如果 A，B 彼此依赖，编译器就会报错。 这就可以抽象为一个有向无环图，如果包的依赖关系是一个有向有环图，就会报错

大前提条件

有向无环图，必有一个入度为 0 的节点。

排序的思路¹：

1. 先找到这个有向图中找到入度为 0 的节点（可能不止一个），那么该点就会在拓扑排序中排在前面。
2. 然后擦掉该节点和从该点出去的边
3. 重复上面的步骤，依次排序

判断有向无环图的思路：

1. 找到这个有向图中找到入度为 0 的节点（可能不止一个）。 如果没有，则此图为有向有环图；反之，执行 (2
2. 然后擦掉该节点和从该点出去的边
3. 重复上面的步骤直到结束，则返回False

Footnotes

1. 拓扑排序的输出可以是一个列表。还是拿依赖举例，输出的先后表示编译器编译的包的顺序 ↩