有向无环图的拓扑排序

首先，介绍一下有向无环图。

从字面上理解:

1. 为有向图
2. 无环

举例，

• 1. 有向的二叉树是特殊的有向无环图。
• 1. 如图（关键部分）

对于有向图来说，深度优先遍历下，若从head出发到结束时出现一条从head的下级节点mid开始指向head的一条路径，则必定此图有环。

拓扑排序

• 首先，拓扑排序的对象肯定是有向无环图中左右的点。
• 其次，若存在路径从a指向b，则拓扑排序结果中a一定在b的前面。
• 最后，拓扑排序的排序规则（没有那么抽象），依次将入度为零的点拿出去，并抹掉它的出度线。

image

有图为例

经过第一次筛选得 A

image

第二次筛选得 B

image

第三次筛选得D

image

第四次筛选的 C，F（若无特殊要求，C,F的顺序是随机的）（这里我们按照字母表来）

image

最后一个是F 所以综上，拓扑排序为 A B D CF E 好，简单明了，帮助理解概念，代码还是要自己敲哦，嘿嘿嘿。