一個復雜的工程通常可以分解成一組小任務的集合完成這些小任務意味著整個工程的完成例如汽車裝配工程可分解為以下任務將底盤放上裝配線裝軸將座位裝在底盤上上漆裝剎車裝門等等任務之間具有先後關系例如在裝軸之前必須先將底板放上裝配線任務的先後順序可用有向圖表示——稱為頂點活動( Activity On Vertex AOV)網絡有向圖的頂點代表任務有向邊(i j) 表示先後關系任務j 開始前任務i 必須完成圖 顯示了六個任務的工程邊( )表示任務在任務開始前完成同樣邊( )表示任務在任務開始前完成邊( )與( )合起來可知任務在任務開始前完成即前後關系是傳遞的由此可知邊( )是多余的因為邊( )和( )已暗示了這種關系
在很多條件下任務的執行是連續進行的例如汽車裝配問題或平時購買的標有需要裝配的消費品(自行車小孩的秋千裝置割草機等等)我們可根據所建議的順序來裝配在由任務建立的有向圖中邊( i j)表示在裝配序列中任務i 在任務j 的前面具有這種性質的序列稱為拓撲序列(topological orders或topological sequences)根據任務的有向圖建立拓撲序列的過程稱為拓撲排序(topological sorting)圖 的任務有向圖有多種拓撲序列其中的三種為 和 序列 就不是拓撲序列因為在這個序列中任務在的前面而任務有向圖中的邊為( )這種序列與邊( )及其他邊所指示的序列相矛盾可用貪婪算法來建立拓撲序列算法按從左到右的步驟構造拓撲序列每一步在排好的序列中加入一個頂點利用如下貪婪准則來選擇頂點從剩下的頂點中選擇頂點w使得w 不存在這樣的入邊( vw)其中頂點v 不在已排好的序列結構中出現注意到如果加入的頂點w違背了這個准則(即有向圖中存在邊( vw)且v 不在已構造的序列中)則無法完成拓撲排序因為頂點v 必須跟隨在頂點w 之後貪婪算法的偽代碼如圖 所示while 循環的每次迭代代表貪婪算法的一個步驟
現在用貪婪算法來求解圖 的有向圖首先從一個空序列V開始第一步選擇V的第一個頂點此時在有向圖中有兩個候選頂點和若選擇頂點則序列V = 第一步完成第二步選擇V的第二個頂點根據貪婪准則可知候選頂點為和若選擇則V = 下一步頂點是唯一的候選因此V = 第四步頂點是唯一的候選因此把頂點加入V 得到V = 在最後兩步分別加入頂點和 得V =
貪婪算法的正確性
為保證貪婪算法算的正確性需要證明 ) 當算法失敗時有向圖沒有拓撲序列; ) 若算法沒有失敗V即是拓撲序列) 即是用貪婪准則來選取下一個頂點的直接結果 ) 的證明見定理 它證明了若算法失敗則有向圖中有環路若有向圖中包含環qj qj + qk qj 則它沒有拓撲序列因為該序列暗示了qj 一定要在qj 開始前完成
定理 如果圖 算法失敗則有向圖含有環路
證明注意到當失敗時| V |<>
數據結構的選擇
為將圖 用C + +代碼來實現必須考慮序列V的描述方法以及如何找出可加入V的候選頂點一種高效的實現方法是將序列V用一維數組v 來描述的用一個棧來保存可加入V的候選頂點另有一個一維數組I n D e g r e eI n D e g r e e[ j ]表示與頂點j相連的節點i 的數目其中頂點i不是V中的成員它們之間的有向圖的邊表示為( i j)當I n D e g r e e[ j ]變為時表示j 成為一個候選節點序列V初始時為空I n D e g r e e[ j ]為頂點j 的入度每次向V中加入一個頂點時所有與新加入頂點鄰接的頂點j其I n D e g r e e[ j ]減對於有向圖 開始時I n D e g r e e [ : ] = [ ]由於頂點和的I n D e g r e e值為因此它們是可加入V的候選頂點由此頂點和首先入棧每一步從棧中取出一個頂點將其加入V同時減去與其鄰接的頂點的I n D e g r e e值若在第一步時從棧中取出頂點並將其加入V便得到了v [ ] = 和I n D e g r e e [ : ] = [ ]由於I n D e g r e e [ ]剛剛變為因此將頂點入棧
程序 給出了相應的C + +代碼這個代碼被定義為N e t w o r k的一個成員函數而且它對於有無加權的有向圖均適用但若用於無向圖(不論其有無加權)將會得到錯誤的結果因為拓撲排序是針對有向圖來定義的為解決這個問題利用同樣的模板來定義成員函數AdjacencyGraph AdjacencyWGraphL 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 [ :n ]中
Network:Topological 的復雜性
第一和第三個f o r循環的時間開銷為(n )若使用(耗費)鄰接矩陣則第二個for 循環所用的時間為(n );若使用鄰接鏈表則所用時間為(n+e)在兩個嵌套的while 循環中外層循環需執行n次每次將頂點w 加入到v 中並初始化內層while 循環使用鄰接矩陣時內層w h i l e循環對於每個頂點w 需花費(n)的時間;若利用鄰接鏈表則這個循環需花費dwout 的時間因此內層while 循環的時間開銷為(n )或(n+e)所以若利用鄰接矩陣程序 的時間復雜性為(n )若利用鄰接鏈表則為(n+e)
程序 拓撲排序
bool Network::Topological(int v[])
{// 計算有向圖中頂點的拓撲次序
// 如果找到了一個拓撲次序則返回t r u e此時在v [ : n ]中記錄拓撲次序
// 如果不存在拓撲次序則返回f a l s e
int n = Ve r t i c e s ( ) ;
// 計算入度
int *InDegree = new int [n+];
InitializePos(); // 圖遍歷器數組
for (int i = ; i <= n; i++) // 初始化
InDegree[i] = ;
for (i = ; 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 = ; i <= n; i++)
if (!InDegree[i]) SAdd(i);
// 產生拓撲次序
i = ; // 數組v 的游標
while (!SIsEmpty()) {// 從堆棧中選擇
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]) SAdd(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);
}
From:http://tw.wingwit.com/Article/program/sjjg/201311/23594.html
