在日常生活中,常用圖來表示一些問題或概念,如IC設計、城市間交通道路規劃、作業調度等。圖和樹一樣,也是一種非線性數據結構。圖和樹的最大差異在于: 樹描述的是數據元素(結點)之間的層次關系,每一層上的數據元素可能和下一層中多個元素(即孩子結點)相關,但只能和上一層中一個元素相關,而圖結構研究兩頂點之間是否相連的關系,在圖中,結點之間的關系是任意的,圖中任意兩個數據元素之間都有可能相關。圖結構提供了簡單的方式來描述一個問題、系統或狀況等。這種圖的先后順序關系便是我們所提到的拓撲圖,我們所要做的事情就是從這些拓撲圖里面提取出符合實際生產需要的拓撲序列,以達到解決實際問題的需要。
然而,基于有向圖的拓撲排序在哪些方面有應用呢?我們都知道一個復雜的工程通常可以分解成一組小任務的集合,完成這些小任務意味著整個工程的完成。例如,汽車裝配工程可分解為以下任務:將底盤放上裝配線,裝軸,將座位裝在底盤上,上漆,裝剎車,裝門等等。任務之間具有先后關系,例如在裝軸之前必須先將底板放上裝配線。任務的先后順序可用有向圖表示——稱為頂點活動( Activity On Vertex, AOV)網絡。再例如,一個建筑工程的過程,通過對我們上面的分析,可以用拓撲圖表示為如下所示,我們可能要問:該項工程或系統能否順利完成?如果一個工程隊在一個時段只能做一件活動,應該按什么順序完成這些活動?還有,比如我們現在的排課問題,也其實是一個拓撲有效序列的求解過程,在此類問題中,課程我們可以用向圖中的結點來表示,然后課程之間的先后關系,我們可以用圖的弧來表示,弧頭是弧尾所指的結點的后導課程,弧尾是弧頭的前驅課程。按照此種定義,我們從中提取出一個課程相互關系的結點元素的序列,便是我們所要求解的拓撲序列。
1 排課問題的描述
每個學期,我們都要對不同的課程進行排課,然而,課程之間有著特殊的制約性質,我們還得考慮,比如計算機核心課程里面的數據結構的前導課程是計算機文化基礎,因此各個課程之間都有著嚴格的前后約束關系。其次,我們假設每個學生選課的情況是一個時間段只能選取一門課程,而且前后的幾個時間段必須是嚴格的連續的關系。再次,各個時間段選取的課程不能是以前已經選取過的課程,在這里我們為了簡單起見,假設選取的時間段為一個學期。最后,我們從建模后的拓撲圖中提取出一個拓撲序列作為一個學生的各個學期的選課順序。綜上所述,該條件下排課問題的建模如下:
1) 各個課程之間有著嚴格的先后順序關系。
2) 兩個相鄰課程之間的跨度為一個時間段,具體就是一個學期。
3) 每個學生每個學期只能選一門課程。
4) 選擇一個拓撲序列便是一個學生的各個學期的選課情況序列。
2有向圖的存儲結構設計以及堆棧的定義
2.1 有向圖的定義與解釋
有向圖是一個二元組,其中:
1) V是非空集合,稱為頂點集。
2) E是V×V的子集,稱為邊集。
直觀來說,若圖中的每條邊都是有方向的,則稱為有向圖。有向圖中的邊是由兩個頂點組成的有序對,有序對通常用尖括號表示,如表示一條有向邊,其中vi是邊的始點,vj是邊的終點。和代表兩條不同的有向邊。
2.2 鄰接矩陣
鄰接矩陣(Adjacency Matrix):是表示頂點之間相鄰關系的矩陣。設G=(V,E)是一個圖,其中V={v1,v2,…,vn}。G的鄰接矩陣是一個具有下列性質的n階方陣:
1) 無向圖的鄰接矩陣一定是對稱的,而有向圖的鄰接矩陣不一定對稱。因此,用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n2個單元來存儲鄰接矩陣;對有n個頂點的無向圖則只存入上(下)三角陣中剔除了左上右下對角線上的0元素后剩余的元素,故只需1 2 ... (n-1)=n(n-1)/2個單元。
2) 無向圖鄰接矩陣的第i行(或第i列)非零元素的個數正好是第i個頂點的度。
3) 有向圖鄰接矩陣中第i行非零元素的個數為第i個頂點的出度,第i列非零元素的個數為第i個頂點的入度,第i個頂點的度為第i行與第i列非零元素個數之和。
4) 用鄰接矩陣表示圖,很容易確定圖中任意兩個頂點是否有邊相連。
2.3 鄰接表
鄰接表是圖的一種鏈式存儲結構。對圖的每個頂點建立一個單鏈表(n個頂點建立n個單鏈表),第i個單鏈表中的結點包含頂點Vi的所有鄰接頂點。又稱鏈接表。其中:
1) 在有向圖的鄰接表中不易找到指向該頂點的弧
2) 在有向圖的鄰接表中,對每個頂點,鏈接的是指向該頂點的弧。
對于有向圖,vi的鄰接表中每個表結點都對應于以vi為始點射出的一條邊。因此,將有向圖的鄰接表稱為出邊表。鄰接表的形式說明如下:
typedef struct node{//邊表結點
int adjvex; //鄰接點域
struct node *next; //鏈域
//若要表示邊上的權,則應增加一個數據域
}EdgeNode;
typedef struct vnode{ //頂點表結點
VertexType vertex; //頂點域
EdgeNode *firstedge;//邊表頭指針
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];//AdjList是鄰接表類型
typedef struct{
AdjList adjlist;//鄰接表
int n,e; 圖中當前頂點數和邊數
}ALGraph; //對于簡單的應用,無須定義此類型,可直接使用AdjList類型。
在本文中將采用的儲存結構便是鄰接表,至于為什么要采用鄰接表而不采用鄰接矩陣,我們將在后面予以分析。
2.4 堆棧的定義以及堆棧在本文中的作用
堆棧是一個不容忽視的概念,但是很多人甚至是計算機專業的人也沒有明確堆棧其實是兩種數據結構。堆棧都是一種數據項按序排列的數據結構,只能在一端(稱為棧頂(top))對數據項進行插入和刪除。要點:堆:順序隨意棧:后進先出(Last-In/First-Out)。
在本文中為了快速有效地輸出拓撲序列,應該要對待輸出的結點進行暫存,并且由于后面待輸出的結點需要與前面已經輸出的結點發生聯系,因此,如果采用數組或者其它的數據結構存儲便會比較麻煩,在這里我們綜合考慮到堆棧的特質,我們采用堆棧作為待輸出結點的緩沖區域。
3 拓撲排序算法的描述
3.1 拓撲排序算法思路
1) 在圖中找一個沒有前驅的頂點,并把它輸出;
2) 從圖中刪除該頂點及由它發出的弧;
3) 重復第1、2步,直到所有頂點都輸出(頂點輸出序列為拓撲序列)或剩余頂點中找不到沒有前驅的頂點(圖中存在回路)。
3.2 拓撲排序偽代碼
1) 計算每個頂點的入度indegree[];
2) 棧S初始化;計數器count初始化;
3) 掃描頂點表,將入度為零的頂點入棧;
4) 當棧S非空時反復循環:
step 3.1 彈出棧頂元素i;打印i;count加1;
step3.2 將頂點i的各個鄰接點的入度減1;
step3.3 將新的入度為0的頂點入棧;
5) if (count
3.3 拓撲排序算法程序代碼
Status ToplogicalSort(ALGraph G){
FindIndegree(G,indegree);
InitStack(S);
for( i=1;i<=G.vexnum;i )
if (!indegree[i]) Push(S,i);
count=0;
while (!StackEmpty(S)){
Pop(S,i);printf(i,G.vertices[i].data); count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc){
k=p->adjvex;
if (- -indegree[k]) Push(S,k);
}//for
}//while
if (count
else return OK;
}//ToplogicalSort
4 實例分析
4.1 排課問題的數學建模
如表1所示,各個課程號代表的含義,以及各個課程相對應的先修課。
如圖1表示了各個課程之間的拓撲圖,其中結點表示課程,弧代表前后兩門課程之間的約束關系。
4.2 實驗模擬初始狀態下各個結點的入度統計與鄰接表的狀態
圖2為各個頂點的入度統計圖;圖3為初始狀態下鄰接表的狀態。
5 實驗結果及分析
5.1 實驗結果
運行的結果表明,本課程安排不存在回路,因此是一個恰當有效的課程安排方案。并且可以產生多種拓撲排序的序列供學生選課方案進行選擇,例如可以是:
1) A,B,C,D,E,F,G
2) A,C,B,D,F,E,G
3) A,C,B,D,E,F,G
5.2 算法復雜度分析
由于本算法采用了一個一階的循環,因此循環體內的語句將執行N個單位次數,另外由于使用了堆棧作為數據暫存結構,則復雜系數為E,因此整個算法的時間復雜度是:O(N E)。
5.3 思考
在本文的算法里面,對于待輸出的結點是采用堆棧作為暫存,而堆棧最大的特點是“先進先出”,但是本算法里面根本沒有運用到堆棧的這個性質,而僅僅是用來作為數據的暫時存儲,這里我們其實也可以采用隊列的方法。
另外,我們也完全可心采用鄰接矩陣的方式對有向圖進行存儲,而不一定是采用鄰接表進行存儲。但是由于在求解每個結點的入度的時候,我們需要掃描整個鄰接矩陣的一行或者一列,而對于N個結點,則需要掃描N*N次,因此時間復雜度則為O(N*N),因此,采用鄰接表的效率要高一些。
參考文獻:
[1] 嚴蔚敏,吳偉民.數據結構C語言版[M].北京:清華大學出版社,2007.
[2] 維斯.數據結構與算法分析C語言描述[M .北京:機械工業出版社,2004.
[3] 周建麗,黃志真.用拓撲排序安排課程順序[J].重慶交通學院學報,1997(4).
[4] 劉聲田,路明.面向對象技術獲取AOV網絡拓撲序列的算法[J].山東電大學報,2005(2).
