拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。 从图中删除该顶点和所有以它为起点的有向边。 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

通常，一个有向无环图可以有一个或多个拓扑排序序列。

拓扑排序的三种方法： 1.无前趋的的顶点优先拓扑排序     思路：在有向图建立完成之后，维护两个点集，一个是当前出度为0的点集，记为①，另一个是出度不为0 的点集，记为②，以及一个记录各个点出度的数组。首先遍历一遍图的全部边，初始化所有点的出度，然后出度为0的点依次 入①，然后将①中的点分别出列，每次出列都需要更新各个点的出度，即把所有跟出列的点邻接的点出度-1（有多条边，则相应减掉边数，一般简单图不会有多重边），直至①变成空集。这个时候，如果②也变成了空集，证明排序成功，否则，原图不存在拓扑排序（图中有环）。最终的排序结果就是从①中出列的点的逆序。 2.无后继的的顶点优先拓扑排序   思路：跟1的方法类似，不过这次是维护根据点的入度进行统计。在有向图建立完成之后，维护两个点集，一个是当前入度为0的点集，记为①，另一个是入度不为0 的点集，记为②，以及一个记录各个点入度的数组。首先遍历一遍图的全部边，初始化所有点的入度，然后入度为0的点依次 入①，然后将①中的点分别出列，每次出列都需要更新各个点的入度，即把所有跟出列的点邻接的点入度-1（有多条边，则相应减掉边数，一般简单图不会有多重边），直至①变成空集。这个时候，如果②也变成了空集，证明排序成功，否则，原图不存在拓扑排序（图中有环）。最终的排序结果就是从①中出列的点的顺序。 3.基于DFS递归的拓扑排序   思路：从图的起点开始进行深度优先搜索，在搜索过程中，把没有后继（相当于出度为0）的点出列（这个过程中，已经出列的点不算是它的前继点，相当于删除了该点），点的出列顺序就是拓扑排序结果的逆序。 下面分析一些hdu上的题目来考察这三个方法的异同。 1.前两种方法本质上是一样的，只不过一个得到的是顺序，一个是逆序，这就根据情况和喜好进行判断，对于关系（a，b）我们直观上认为在图中是这样的 a -> b, 然而，在某些题目中（a，b）的意义可能是 a>b，这就不大符合我们的直观理解（一般认为图的上端好，大……），不过这都不影响排序结果，各求所需就好。 2.未经优化的DFS拓扑排序，在图存在环的时候会进入死循环，因此，要注意确保图没有环，或者最好进行优化再使用。 3.维护出度为0以及DFS拓扑得到的结果是逆序！ 4.拓扑排序结果不一定唯一，注意题目要求。 5.DFS拓扑需要知道图的起点，否则不能深搜整个图，也就没有得到完整的拓扑排序结果。 6.在维护点集的拓扑中，加入当前出度（入度）为0的点大于1个，则得到的拓扑排序结果不唯一