| 拓樸排序 ( Topological Sort ) |
| |
| 定義 |
| 若在 AOV-network
中，Vi 是 Vj 的前行者，則在線性的排列中，Vi 一定在 Vj 的前面，此種特 |
| 性稱之為拓樸排序 (
topological sort ) 。 |
| |
| 尋找 AOV-network
拓樸排序的過程如下： |
| |
| (１) 在
AOV-network 中任意挑選沒有前行者的節點。 |
| (２) 輸出此頂點，並將該頂點所連接的邊刪除。重覆步驟 (１)
及步驟 (２) ，一直到全部的頂點 |
| 皆輸出為止。 |
|
| 【範例】 |
| 求下面 AOV-network
的拓樸排序 |
| |
|
|
| |
| 【解答】 |
|
| 1. 輸出 V1 ，並刪除
< V1,V2 > 與
< V1,V6 > 兩個邊 |
| |
|
|
| |
| 2. 輸出 V2 ，並刪除
< V2,V3 > 與
< V2,V4 > 兩個邊 |
| |
|
|
| |
| 3. 輸出 V6 ，並刪除
< V6,V4 > 與
< V6,V5 > 兩個邊 |
| |
|
|
| |
| 4. 輸出 V3，並刪除
< V3,V7 > 與
< V3,V5 > 兩個邊 |
| |
|
|
| |
| 5. 輸出 V4 ，並刪除
< V4,V5 > |
| |
|
|
| |
| 6. 輸出 V7 ，並刪除
< V7,V8 > |
| |
|
|
| |
| 7. 輸出 V5 ，並刪除
< V5,V8 > |
|
|
|
| |
| 8. 輸出 V8 |
| |
| 其所得的資料輸出順序為 1 ,
2 , 6 , 3 , 4 , 7 , 5 , 8 |
| |
| PS. AOV-network
的拓樸排序並不是只有唯一的一種排列順序。 |
| |
| 演算法 |
|
| void topsort (
hdnodes , graph[] , int n ) |
| { |
| int i , j , k ,
top ; |
| node_pointer ptr ; |
| top = -1
; |
| for ( i = 0 ; i
< n ; i++ ) |
| if (
!graph[i].count ) { |
| graph[i].count = top ; |
| top = i
; |
| ｝ |
| for ( i = 0 ; i
< n ; i++ ) |
| if ( top == -1
) { |
| fprintf (
stderr, "\n Network has a cycle. Sort terminated. \n" )
; |
| exit (1)
; |
| } |
| else
{ |
| j = top
; |
| top =
graph[top].count ; |
| printf (
"v%d, " j ) ; |
| for ( ptr =
graph[j].link ; ptr ; ptr = ptr->link ) { |
| k = ptr
-> vertex ; |
| graph[k].count -- ; |
| if (
!graph[k].count ) { |
| graph[k].count = top ; |
| top = k
; |
| } |
| } |
| } |
| } |
| |
| 本演算法的時間複雜度為 O(e+n) |
| |
| 相關名詞說明 |
| |
| AOV-network
|
| |
| 在一個有方向圖形中，每一頂點代表工作 ( task ) 或活動 ( activity ) ，而邊表示工作之間的優先 |
| 順序 ( precedence
relations ) 。即邊 < Vi,Vj > 表示 Vi 的工作處理完後才可以處理 Vj 的工作。 |
| 此種有方向圖形稱之為 activity on vertex network 或 AOV-network 。 |
| |
| 立即前行者 ( immediate predecessor ) 與立即後繼者 ( immediate successor ) |
| |
| 若在有方向圖形 G
中有一邊 < Vi,Vj
> ，則稱 Vi
是 Vj 的立即前行者，而 Vj 是 Vi 的立即後繼 |
| 者。 |
| |
| 前行者 ( predecessor ) 與後繼者 ( successor
) |
| |
| 在 AOV-network
中，假若由頂點 Vi
到頂點 Vj
存在有一條路徑，則稱 Vi
是 Vj 的前行者，而 Vj |
| 是 Vi 的後繼者。 |
|