基于邻接表结构的拓扑排序的全序列算法研究

薛春艳

（厦门大学嘉庚学院信息科学与技术学院，厦门 361000）

基于邻接表结构的拓扑排序的全序列算法研究

薛春艳

（厦门大学嘉庚学院信息科学与技术学院，厦门 361000）

拓扑排序是有向无环图的用来描述各活动间的先后关系的重要应用。利用拓扑排序算法能得到图中的各活动的线性序列，同时这个序列满足各活动在图中体现的先后关系，即拓扑序列。常用的求解拓扑排序方法是求得一个拓扑序列即可。为了增强算法的实用价值，给出求解有向无环图的所有拓扑序列的方法，并讨论算法的原理及代码实现，验证全拓扑排序算法的实用性和正确性。

拓扑排序；全序列；邻接表

0 引言

有向无环图在实际应用中经常用来描述工程或者系统的进行过程。如工程施工图、学生选课关系图等。在图中，用顶点表示活动，用有向边表示活动间的先后关系，这种有向图称为AOV网(Activity On Vertex Network)。将AOV网中的各个顶点排成一个线性序列，使各顶点在序列中保持其在图中体现出来的先后关系，这个过程称为拓扑排序。由此得到的线性序列称为拓扑序列[1]。

求有向无环图的拓扑序列的意义在于可以根据拓扑序列对图中活动进行串行地安排，从而提高活动安排的效率。如学生课程间的安排、生产控制过程的优化、工程施工的过程管理等[2]。

有向无环图的拓扑序列通常情况下是不唯一的，常用的拓扑排序方法当得到一个拓扑序列后就结束了；在很多应用中，只求出一个拓扑序列是不够的，需要得到的该图的全部可能的拓扑序列，再根据相关的要求选出最佳的拓扑序列。

1 拓扑排序算法的存储结构

在计算机中实现时，有向无环图采用了邻接表作为存储结构。同时在基本的邻接表的基础上进行了改进，为了实现算法的方便，在顶点结构中加了一项，用来存放该顶点入度的值。通过这个入度的值可以进行下面两操作：

（1）判断当前顶点是否是无前驱的顶点：即判断其入度是否为0；

（2）输出顶点后，需要删除该顶点和所有以它为尾的弧的操作：即将以该顶点为弧尾的另一端的弧头顶点的入度减1。

同时，需要设一个栈结构来存放拓扑排序过程中所有入度为零的顶点[3]。改进后的有向无环图的存储结构如下：

以图1为例，图2是图1的邻接表结构示意图。

图1 无向图G

图2 无向图G的邻接表示意图

2 拓扑排序的算法思想

拓扑排序的算法思想是：

（1）在有向无环图中任选一个没有前驱的顶点（无前驱的顶点可能有多个）并且输出。

（2）删除该顶点以及所有由该顶点发出的弧。

重复上述两步，直到图中所有顶点全部输出为止。

其伪代码如下：

（1）栈S初始化；

（2）扫描顶点表，将所有无前驱的顶点入栈；

（3）当栈S非空时循环

栈顶元素vj出栈；输出vj；

顶点vj的各个邻接点的入度减1，若间后入度为0，则将该顶点入栈S。

若所有的顶点都已输出，就表明所输出的序列即为所求的该有向无环图的拓扑序列。

3 全拓扑排序算法的原理与实现[3]

全拓扑排序采用了邻接表作为图的存储结构，通过深度优先搜索获得序列，利用栈结构存储无前驱的顶点，利用队列结构存储所有可能的待检测的序列，利用穷举法来判断是否符合拓扑排序的要求，最终求出所有符合要求的解。

（1）统计所有入度为0的顶点，穷举出由这些顶点开始所能构造的所有可能的顶点序列；

（2）判断当前序列是否是合法的拓扑排序，如果是，则输出该序列，转（1）。

（3）否则转（2），直到所有可能序列都完成检测为止。

全拓扑排序函数代码如下：

4 程序运行结果

根据图1收入边数：6和9条边的信息（以“起点编号 重点编号”格式输入），最终求得图G的全拓扑序列为6个，具体情况如图3所示。见图3：

图3 图G的全拓扑序列求解结果

5 结语

本文给出了全拓扑序列算法的基本思想和具体编程实现过程。全拓扑排序算法思想简单明了，时间复杂度和空间复杂度适当。求解全拓扑排序目的是为了求解特殊条件下的最佳的拓扑序列。因此，若在获得备选序列的过程中加上贪心规则，算法的性能还能得到进一步提高。

[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.

[2]王琼.拓扑排序算法的拓展研究[J].计算机工程与应用，2006-24.

[3]朱立华，王汝传.AOV网中全拓扑排序算法的设计及应用[J].微机发展，2004-14.

Topology Sorting;All Sort;Adjacency List

Research on the Algorithm for all Topology Sorting Based on Adjacency List Structure

XUE Chun-yan
（College of Information Science and Technology,Xiamen University Tan Kah Kee College,Xiamen 361000）

Topology sort is an important application of a Directed Acyclic Graph for the relations between activities which in the DAG.Topology sort algorithm can get a linear sequence of each activity in this DAG,this sequence of activities meets all embodied relationship in the DAG, namely topological sequence.Usually,the topological sorting method obtains a topological sequence.In order to enhance the practical value of the algorithm,presents a method to get all the topology sequence of the DAG,and discusses the principle and the code algorithm, verifies the correctness and practicality of the full topological sorting algorithm.

1007-1423（2016）19-0074-03

10.3969/j.issn.1007-1423.2016.19.018

薛春艳（1976-），女，吉林辽源人，硕士研究生，副教授，研究方向为数字图像处理、算法设计与分析、数据库

2016-04-14

2016-07-02