拓扑排序

2020-04-25 本文已影响0人我是小曼巴

概念

定义
拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条从 $v_{i}$ 到 $v_{j}$ 的路径，那么在排序中 $v_{j}$ 必定在 $v_{i}$ 的后面；反之不一定成立。

性质
1.如果图中存在圈，那么拓扑排序是不可能的，因为对于圈上的两个顶点v和w，v先于w的同时，w也先于v。
2.拓扑排序不必是唯一的，任何合理的排序都是可以的。

举例

图1：一个有向无圈图

在图1中， $v_{1},v_{2},v_{5},v_{4},v_{3},v_{7},v_{6}$ 和 $v_{1},v_{2},v_{5},v_{4},v_{7},v_{3},v_{6}$ 两个都是拓扑排序。

如果用一个有向无圈图表示大学的课程先修结构，那么这个图的拓扑排序就是不破坏课程结构要求的任意的课程序列。

一个简单的求拓扑排序的算法是先找到任意一个没有入边（入度为0）的顶点，然后显示出该顶点，并将它及其边一起从图中删除。然后，我们对图的其余部分同样应用这样的方法处理。

算法一：

方法findNewVertextOfIndegreeZero方法是对顶点数组的简单扫描，找出一个尚未被分配拓扑编号的且入度为0的顶点。如果这样的顶点不存在，那么返回null，且说明该图有圈。此算法的运行时间为 $O(|V|^{2})$ 。

算法二：

首先对每个顶点计算其入度，将每个入度为0的顶点放入到一个队列中。当队列不空时，删除一个顶点v，并将与v邻接的所有顶点的入度减1。这些邻接顶点中，只要有一个入度降为0，就把该节点放入到队列中。此时，拓扑顺序就是顶点的出队顺序。这个算法的运行时间为 $O(|E|+|V|)$ 。

对图1应用拓扑排序的结果