7.6　拓扑排序

在现实生活中,通常把某个项目或某个生产流程当成一个工程,大工程常常划分为许多较小的子工程,这些子工程之间存在优先关系,例如,其中的某些子工程必须在另外一些子工程完成之后开始。

那么,如何确定该工程能否顺利进行,以及掌握子工程的执行过程呢？有向图无环图的拓扑排序可以解决这个问题。

用有向图表示一个工程,顶点代表子工程,称为活动；有向边表示活动的先后顺序,即边的起点活动是终点活动的先决条件,这类有向图称为AOV网。如果在AOV网G中,从顶点v_i到顶点v_j有一条路径,则活动v_i必然先于活动v_j完成,按照这个原则将G中所有顶点排序,使每个活动的所有前驱活动都排在该活动之前,该过程称为拓扑排序,得到的顶点序列为拓扑序列。

例如,安排计算机专业必修课程的课表。计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程如图7－35所示。

图7－35　计算机专业必修课程

按照课程之间的关系,可得到如图7－36所示的AOV网。

图7－36　计算机专业必修课程AOV网

没有先修课的课程可以先上课,如C₁、C₂；而有先修课的课程,必须在学完其先修课程之后才能开始,如C₃必须在学完C₂和C₁之后再学,C₅也必须在学完C₂之后再学；没有先修关系的课程,其排课的先后次序则可以任意,如C₅和C₄,可以先选修C₅,也可以先选修C₄。排课方案可以是:C₀,C₁,C₂,C₄,C₃,C₅,C₇,C₈,C₆；还可以排列为C₀,C₇,C₈,C₁,C₄,C₂,C₃,C₆,C₅。这两个序列便是AOV网的拓扑序列,可见AOV网的拓扑序列并不是唯一的。

在拓扑排序中,每个顶点都必须排在它的后继顶点之前。那么排在最前面的顶点一定不能是其他任何顶点的后继顶点,即该顶点没有前趋顶点,入度值为0。每当AOV网中的一个顶点表示的活动完成时,该顶点的所有后继顶点均少了一个前驱条件,即入度值减1。入度值为0的顶点可以作为下一个要执行活动的备选项。拓扑排序的方法如下。

（1）从AOV网中选择一个入度为0的顶点且输出该顶点。

（2）从AOV网中删掉该顶点及其所有以该顶点为起点的边。

反复执行这两个步骤,直到所有的顶点都被输出,输出的序列就是这个AOV网的拓扑序列。图7－37显示了拓扑排序的执行过程。

其拓扑序列为:v₀,v₅,v₃,v₄,v₂,v₁（不一定唯一）。

为了方便地修改顶点的入度值,可以定义一个一维数组来记录各个顶点的入度值。初始化时,数组中填入各顶点的入度值。每个顶点的入度值随着顶点的输出而动态变化,入度为0即该顶点没有前驱顶点,为了减少重复检测入度为0的结点,这里借助队列来保存入度为0的顶点。在队列非空时进行入度为0的顶点的出入队和输出,其详细算法如下。

（1）计算每个结点的入度,保存在数组indegree中。

（2）检查indegree中的每个元素,将入度为0的结点入队。

图7－37　拓扑排序过程

（3）不断从队列中将入度为0的结点出队,输出此结点,并将该结点的后继结点的入度减1；如果某个邻接点的入度为0,则将其入队。反复操作直至队空。

该算法的C语言实现如下。

对有n个顶点和e条弧的有向图,计算各顶点的入度的时间复杂度为O（e）；建立零入度顶点栈的时间复杂度为O（n）；在拓扑排序过程中,若有向图无环,则每个顶点进一次栈、出一次栈,入度减1的操作在while语句中总共执行e次,所以总的时间复杂度为O（n＋e）。

并不是任何有向图的顶点都可以排成拓扑序列,有向环图是不能的。如果有向图存在环,意味着某项活动将以自己为先决条件,显然无法形成拓扑序列。求有向图顶点的拓扑序列,若图中所有顶点都出现在它的拓扑序列中,则该图中一定不存在环,否则就会有环。有环存在的AOV网对应的工程不能顺利进行,无环存在的AOV网的拓扑序列即对应于工程子活动的执行顺序。