基于鄰接表結構的拓撲排序的全序列算法研究

薛春艷

（廈門大學嘉庚學院信息科學與技術學院，廈門 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