一個復雜的工程通?？梢苑纸獬梢唤M小任務的集合，完成這些小任務意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務之間具有先后關系，例如在裝軸之前必須先將底板放上裝配線。任務的先后順序可用有向圖表示——稱為頂點活動（ 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）及其他邊所指示的序列相矛盾?？捎秘澙匪惴▉斫⑼負湫蛄小Ｋ惴ò磸淖蟮接业牟襟E構造拓撲序列，每一步在排好的序列中加入一個頂點。利用如下貪婪準則來選擇頂點：從剩下的頂點中，選擇頂點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 | 

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 ) ; } 

} 

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

LinkedStack 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); 

}