『算法-ACM 竞赛-图论』拓扑排序

拓扑排序

在图论中，拓扑排序（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 个，则得到的拓扑排序结果不唯一