基础-7：拓扑排序

在前面的课程中，讲述了图的两种基本表示方法：邻接表和邻接矩阵，以及两种基本的遍历：广度遍历和深度遍历。在此基础上，我们一起探讨图的第一个基本的应用：拓扑排序。

什么叫拓扑排序？请大家先看下面的一张图：

图1:课程表拓扑关系例子

所谓拓扑排序，就是根据有向图中的偏序关系，对图中的节点进行排序。对于图1中的例子而言，排课老师的任务是：根据课程之间的先修关系，每个学期合理安排课程，保证每门课的先修课都必须安排在这门课的前面。如果是你，你如何排？

在进一步思考之前，首先应该明白，只有有向无环图才有拓扑排序，无向图和有环的有向图都不可能有拓扑排序。

在没有学习图论之前，大家的想法可能是：先找到所有入度为0的节点，然后顺着这些节点继续寻找，但是顺着这些节点后面的寻找规则是什么？如C9的入度为0，顺着C9，有C10、C11和C12，这三者又是什么关系呢？进一步，可以发现C10是C12的先修课程，也就是拓扑排序中，C9必须安排在C10之前，C10必须安排在C12之前。但是到现在为止，我们并未明确表述这些规则是什么？

拓扑排序的根本目的是：根据图节点之间的偏序关系，对图进行排序。偏序关系在有向图中的表现就是有向边，再进一步，我们可以看作是在图的遍历过程中对其进行排序。考虑前面课程中学习的广度遍历和深度遍历，广度遍历是对外逐层扩展，主要用于求源节点到所有其它节点的最短路径，体现的是距离；深度遍历则是对当前节点，依据有向边对当前的邻接节点继续深入遍历，整个遍历过程其实质就体现了拓扑排序中的关系。

以C9、C10、C11、C12为例，对其拓扑排序的可能包括(三种典型的，还有其它类似几种可能)：

• C9(1/12) -> C10(2/5) -> C12(3/4) -> C11(6/11) -> C6(7/10) -> C8(8/9)
• C9(1/12) -> C12(2/3) -> C10(4/5) -> C11(6/11) -> C6(7/10) -> C8(8/9)
• C9(1/12) -> C11(2/7) -> C6(3/6) -> C8(4/5) -> C12(8/9) -> C10(10/11)

上面列出的节点中的括号中的数据C9(m/n)，m表示发现节点的时间，n表示当前节点的所有邻接节点已全部发现的完成时间（忘记的童鞋请查阅：前面课程），如果按照完成时间倒排会是什么？上面的三种的排列结果分别为：

• C9, C11, C6, C8, C10, C12
• C9, C11, C6, C8, C10, C12
• C9, C10, C12, C11, C6, C8

仔细观察，上面的排序结果均满足前文提到的先修关系（提示：拓扑排序可能不止一种），即：深度遍历的完成时间倒排序即是拓扑排序结果，下面对其进行分析证明：

分析：假设图G(V, E)，对于图中任意节点v，v.d表示发现节点v的时间，v.f表示v的所有邻接节点遍历完成的时间, 若有（u, v）是E中的一条边，只需要证明v.f < u.f。 对E中的任意边（u, v），在深度遍历中，当通过u对v进行探索时，v肯定不是灰色（如果v是灰色，则表示v的邻接节点深度遍历还未结束，u肯定是v的后继节点，则u和v构成了环，这种情况下，不可能存在拓扑排序），如果v是白色，则必然有v.f < u.f成立；如果v是黑色，则表示v的邻接节点已经遍历完成，v.f < u.f显然成立。由此：结论成立。（注意：深度遍历中，节点v为白色表示还未发现v，为灰色表示v被发现，并开始访问其邻接节点，为黑色表示v的所有邻接节点已访问完毕，结束v的访问）

因此，图的深度遍历中记录的遍历访问结束时间就是拓扑排序的依据，当然，其原理其实也很简单，童鞋们只需仔细把这个证明分析推敲一遍就形了。相应的源代码请见（ https://github.com/bjutJohnson/Algorithms/blob/master/src/graph/graph_manager.go ）中的TopologySort函数。