薛春艳

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

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

薛春艳

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

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

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

0 引言

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

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

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