q4演算法

『壹』 拓撲排序的應用

一個復雜的工程通常可以分解成一組小任務的集合，完成這些小任務意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務之間具有先後關系，例如在裝軸之前必須先將底板放上裝配線。任務的先後順序可用有向圖表示——稱為頂點活動（ Activity On Vertex, AOV）網路。有向圖的頂點代表任務，有向邊(i, j) 表示先後關系：任務j 開始前任務i 必須完成。圖1 - 4顯示了六個任務的工程，邊（ 1 , 4）表示任務1在任務4開始前完成，同樣邊（ 4 , 6）表示任務4在任務6開始前完成，邊（1 , 4）與（4 , 6）合起來可知任務1在任務6開始前完成，即前後關系是傳遞的。由此可知，邊（1 , 4）是多餘的，因為邊（1 , 3）和（3 , 4）已暗示了這種關系。

在很多條件下，任務的執行是連續進行的，例如汽車裝配問題或平時購買的標有「需要裝配」的消費品（自行車、小孩的鞦韆裝置，割草機等等）。我們可根據所建議的順序來裝配。在由任務建立的有向圖中，邊（ i, j）表示在裝配序列中任務i 在任務j 的前面，具有這種性質的序列稱為拓撲序列（topological orders或topological sequences)。根據任務的有向圖建立拓撲序列的過程稱為拓撲排序（topological sorting）。圖1 - 4的任務有向圖有多種拓撲序列，其中的三種為1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓撲序列，因為在這個序列中任務4在3的前面，而任務有向圖中的邊為（ 3 , 4），這種序列與邊（ 3 , 4）及其他邊所指示的序列相矛盾。可用貪婪演算法來建立拓撲序列。演算法按從左到右的步驟構造拓撲序列，每一步在排好的序列中加入一個頂點。利用如下貪婪准則來選擇頂點：從剩下的頂點中，選擇頂點w，使得w 不存在這樣的入邊（ v,w），其中頂點v 不在已排好的序列結構中出現。注意到如果加入的頂點w違背了這個准則（即有向圖中存在邊（ v,w）且v 不在已構造的序列中），則無法完成拓撲排序，因為頂點v 必須跟隨在頂點w 之後。貪婪演算法的偽代碼如圖1 3 - 5所示。while 循環的每次迭代代表貪婪演算法的一個步驟。

現在用貪婪演算法來求解圖1 - 4的有向圖。首先從一個空序列V開始，第一步選擇V的第一個頂點。此時，在有向圖中有兩個候選頂點1和2，若選擇頂點2，則序列V = 2，第一步完成。第二步選擇V的第二個頂點，根據貪婪准則可知候選頂點為1和5，若選擇5，則V = 2 5。下一步，頂點1是唯一的候選，因此V = 2 5 1。第四步，頂點3是唯一的候選，因此把頂點3加入V

得到V = 2 5 1 3。在最後兩步分別加入頂點4和6 ，得V = 2 5 1 3 4 6。

1. 貪婪演算法的正確性

為保證貪婪演算法算的正確性，需要證明： 1) 當演算法失敗時，有向圖沒有拓撲序列； 2) 若

演算法沒有失敗，V即是拓撲序列。2) 即是用貪婪准則來選取下一個頂點的直接結果， 1) 的證明見定理1 3 - 2，它證明了若演算法失敗，則有向圖中有環路。若有向圖中包含環qj qj + 1.qk qj , 則它沒有拓撲序列，因為該序列暗示了qj 一定要在qj 開始前完成。

定理1-2 如果圖1 3 - 5演算法失敗，則有向圖含有環路。

證明注意到當失敗時| V |<n, 且沒有候選頂點能加入V中，因此至少有一個頂點q1 不在V中，有向圖中必包含邊（ q2 , q1）且q2 不在V中，否則， q1 是可加入V的候選頂點。同樣，必有邊（q3 , q2）使得q3 不在V中，若q3 = q1 則q1 q2 q3 是有向圖中的一個環路；若q3 ≠q1，則必存在q4 使（q4 , q3）是有向圖的邊且q4 不在V中，否則，q3 便是V的一個候選頂點。若q4 為q1 , q2 , q3 中的任何一個，則又可知有向圖含有環，因為有向圖具有有限個頂點數n，繼續利用上述方法，最後總能找到一個環路。

2. 數據結構的選擇

為將圖1 - 5用C + +代碼來實現，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點。一種高效的實現方法是將序列V用一維數組v 來描述的，用一個棧來保存可加入V的候選頂點。另有一個一維數組I n D e g r e e，I n D e g r e e[ j ]表示與頂點j相連的節點i 的數目，其中頂點i不是V中的成員，它們之間的有向圖的邊表示為（ i, j）。當I n D e g r e e[ j ]變為0時表示j 成為一個候選節點。序列V初始時為空。I n D e g r e e[ j ]為頂點j 的入度。每次向V中加入一個頂點時，所有與新加入頂點鄰接的頂點j，其I n D e g r e e[ j ]減1。對於有向圖1 - 4，開始時I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。由於頂點1和2的I n D e g r e e值為0，因此它們是可加入V的候選頂點，由此，頂點1和2首先入棧。每一步，從棧中取出一個頂點將其加入V，同時減去與其鄰接的頂點的I n D e g r e e值。若在第一步時從棧中取出頂點2並將其加入V，便得到了v [ 0 ] = 2，和I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。由於I n D e g r e e [ 5 ]剛剛變為0，因此將頂點5入棧。

程序1 3 - 2給出了相應的C + +代碼，這個代碼被定義為N e t w o r k的一個成員函數。而且，它對於有無加權的有向圖均適用。但若用於無向圖（不論其有無加權）將會得到錯誤的結果，因為拓撲排序是針對有向圖來定義的。為解決這個問題，利用同樣的模板來定義成員函數AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。這些函數可重載N e t w o r k中的函數並可輸出錯誤信息。如果找到拓撲序列，則Topological 函數返回t r u e；若輸入的有向圖無拓撲序列則返回f a l s e。當找到拓撲序列時，將其返回到v [ 0 :n- 1 ]中。

3. Network:Topological 的復雜性

第一和第三個f o r循環的時間開銷為(n )。若使用（耗費）鄰接矩陣,則第二個for 循環所用的時間為(n2 )；若使用鄰接鏈表,則所用時間為(n+e)。在兩個嵌套的while 循環中，外層循環需執行n次，每次將頂點w 加入到v 中，並初始化內層while 循環。使用鄰接矩陣時，內層w h i l e循環對於每個頂點w 需花費(n)的時間；若利用鄰接鏈表，則這個循環需花費dwout 的時間，因此，內層while 循環的時間開銷為(n2 )或(n+e)。所以，若利用鄰接矩陣，程序1 3 - 2的時間復雜性為(n2 )，若利用鄰接鏈表則為(n+e)。

程序13-2 拓撲排序

bool Network::Topological(int v[])

{// 計算有向圖中頂點的拓撲次序

// 如果找到了一個拓撲次序，則返回t r u e，此時，在v [ 0 : n - 1 ]中記錄拓撲次序

// 如果不存在拓撲次序，則返回f a l s e

int n = Ve r t i c e s ( ) ;

// 計算入度

int *InDegree = new int [n+1];

InitializePos(); // 圖遍歷器數組

for (int i = 1; i <= n; i++) // 初始化

InDegree[i] = 0;

for (i = 1; i <= n; i++) {// 從i 出發的邊

int u = Begin(i);

while (u) {

I n D e g r e e [ u ] + + ;

u = NextVe r t e x ( i ) ; }

}

// 把入度為0的頂點壓入堆棧

LinkedStack<int> S;

for (i = 1; i <= n; i++)

if (!InDegree[i]) S.Add(i);

// 產生拓撲次序

i = 0; // 數組v 的游標

while (!S.IsEmpty()) {// 從堆棧中選擇

int w; // 下一個頂點

S . D e l e t e ( w ) ;

v[i++] = w;

int u = Begin(w);

while (u) {// 修改入度

I n D e g r e e [ u ] - - ;

if (!InDegree[u]) S.Add(u);

u = NextVe r t e x ( w ) ; }

}

D e a c t i v a t e P o s ( ) ;

delete [] InDegree;

return (i == n);

}