[ 資料結構 小學堂 ] 圖形結構 : AOV 網路與拓樸排序

前言 : 
以圖形嚴謹的定義來說, AOV 網路就是一種有向圖形, 在這個有向圖形中的每一個節點代表一項工作或必須執行的動作, 而那些有方向性的邊則代表了工作與工作間存在的先後關係順序. 也就是說, Vj> 表示必須先處理完 Vi 的工作, 才可以進行 Vj 的工作. 舉個例子來說, 要完成地下化高速鐵路這個大工程, 必須要把幾個重要且必須先行完成的細項工作列出來, 在把可以同時進行的工作列出來, 依重要性及先後關係畫成圖形 : 
 
如上圖, 要完成高速鐵路的興建有個關鍵點就是土地的取得. 亦即土地未取得前, 那些土建開工, 軌道工程及機電工程等工作事項則無法進行. 在了解 AOV 網路的基本概念後, 有如下的專有名詞需要知道 : 
1. 先行者 : 若頂點Vi 的工作必須先完成後, 才能進行 Vj 頂點的工作, 則稱 Vi 為 Vj 的 "先行者". 
2. 拓樸排序與拓樸序列 : 如果在 AOV 網路中, 具有的部分次序關係 (亦即有某幾個頂點為先行者), 拓樸排序功能就是將這些部分次序 (Partial Order) 的關係, 轉換成線性次序 (Linear Order) 的關係. 例如 i 是 j 的先行者, 在線性次序中, i 仍排在 j 的前面, 具有這種特性的線性次序就稱為拓樸序列 (Topological Order). 底下為拓樸排序與拓樸序列作一摘要性說明 : 

1. 產生拓樸序列必須存在的條件是一個非循環圖形, 由於 AOV 圖形代表各項小工作的先後完成順序圖, 所以沒有循環問題, 所以 AOV 網路經過拓樸排序後可以產生有線性次序關係拓樸序列.
2. 在一個 AOV 網路經過拓樸排序所產生的拓樸序列可能有一個以上, 亦即拓樸序列不是唯一的.

拓樸排序實作 : 
拓樸排序的步驟 : 
步驟1 : 尋找圖形中任何一個沒有先行者的頂點. 
步驟2 : 輸出此頂點, 並將此頂點的所有邊刪除. 
步驟3 : 重複上面兩個步驟來處理所有的頂點. 
這裡範例參考下圖為修習大學課程的 AOV 網路, 必須先修完 B 才能選修 C. 請決定修課的拓樸排序結果 : 
 
步驟1 : 輸出沒有先行者的 A, 並把 A 頂點的所有邊線刪除. (拓樸排序結果 : A) 
步驟2 : 輸出沒有先行者的 B,E,G 並把該頂點的所有邊線刪除. (拓樸排序結果 : A,B,E,G) 
步驟3 : 輸出沒有先行者的 C,F,H 並把該頂點的所有邊線刪除. (拓樸排序結果 : A,B,E,G,C,F,G) 
步驟4 : 輸出沒有先行者的 D,I 並把該頂點的所有邊線刪除. (拓樸排序結果 : A,B,E,G,C,F,G,D,I) 
步驟5 : 輸出沒有先行者的 J 並把 J 頂點的所有邊線刪除. (拓樸排序結果 : A,B,E,G,C,F,G,D,I,J) 
也就是說, 如果你是依照上述順序選修課程, 就一定不會發生因為該修的科目未修而被擋修的情形. 由上例我們可以知道拓樸排序所輸出的結果不一定是唯一解, 如果同時有兩個以上的頂點都沒有先行者, 那麼結果就不是唯一解. 另外如果 AOV 網路中每一個頂點都有先行者, 那表示此網路含有循環而無法進行拓樸排序. 

AOE 網路 : 
之前所談的 AOV 網路是指在有向圖形中的頂點表示一項工作, 而邊表示頂點之間的先後關係. 下面還要來介紹一個新名詞 : AOE (Activity On Edge). 所謂 AOE 是指事件 (Event) 的行動 (Action) 在邊上的有向圖形. 其中的頂點做為各 "進入事件" (Incident in Edge) 的匯集點, 當所有 "進入邊事件" 的行動全部完成後, 才可以開始 "外出事件" (Incident Out Edge) 的行動. 在 AOE 網路會有一個源頭頂點與目的的頂點. 從源頭頂點開始計時執行各邊上事件的行動, 到目的頂點完成為止所需的時間為所有事件完成的時間總花費. 

臨界路徑 : 
AOE 完成所需要的時間是由一條或數條的臨界路徑 (Critical Path) 所控制. 所謂臨界路徑就是 AOE 有向圖形從源頭到目的頂點所需花費時間最長的一條有方向性的路徑, 當有一條以上的花費時間相等, 而且都是最長, 想縮短整個 AOE 完成的花費時間, 必須設法縮短臨界路徑各邊行動所需花費的時間. 
臨界路徑乃是用來決定一個計畫至少需要多少時間才可以完成. 亦即在 AOE 有向圖形中從源頭到目的頂點最長時間的路徑, 請參考下圖 : 
 
上圖代表 12 個 Action (a1 ~ a12) 及 10 個 Event (V1 ~ V10). 我們先來看看一些重要相關定義 : 
1. 最早時間 (Earlest Time) : 
AOE 網路上頂點的最早時間為該頂點最早可以開始其外出邊事件 (Incident Out Edge) 的時間, 它必須由最慢完成的進入邊事件所控制, 我們用 TE 表示. 
2. 最晚時間 (Latest Time) : 
AOE 網路中頂點的最晚時間為該頂點最慢可以開始其外出邊事件 (Incident Out Edge) 而不會影響整個 AOE 網路完成的時間. 它是由外出邊事件 (Incident Out Edge) 中最早要求開始者所控制. 我們以 TL 表示. 
至於 TE 及 TL 的計算原則為 : 

TE : 由前往後 (源頭到目的), 若第 i 項工作前面有幾項工作有好幾個完成時段, 取其中最大值.
TL : 由後往前 (目的到源頭), 若第 i 項工作後面幾項工作有好幾個完成時段, 取其中最小值.

3. 臨界頂點 (Critical Vertex) : 
AOE 網路中頂點 TE=TL, 我們稱它為臨界頂點. 從源頭頂點到目的頂點的各個臨界頂點可以構成一條或數條臨界路徑. 只要控制好臨界路徑所花費的時間, 就不會 Delay 工作進度. 如果集中火力縮短臨界路徑所花費的時間, 就可以加速整個計畫完成的速度. 我們以下圖為例來簡單說明如何決定臨界路徑 : 
 
上圖的紅色路徑即為臨界路徑, 臨界路徑上的 TL=TE. 其臨界路徑求法如下 : 
1. 先求出 TE. : 

- 在 V2, 其 TE 為 5.
- 在 V5, 往前面看, 最長路徑為8 (V1到V2到V5=8 > V1到V3到V5=6), 故 TE=8.
- 在 V6, 往前面看, 最長路徑為13
- 在 V8, 往前面看, 最長路徑為18 (V1到V5到V8=15 < V1到V6到V8=18), 故TE=18.
- 在 V9, 往前面看, 最長路徑為20.
- 在 V10, 往前面看, 最長路徑為25.

2. 接著求出 TL : 

- 由V10的TE往前推, 因為V10 為目的點, 所以其 TL=TE=25.
- V9 的 TL = V10 的 TL - 5 = 20, 故 V9 的 TL=20.
- V7 的 TL = V9 的 TL - 3 = 17, 故 V7 的 TL=17.
- V8 的 TL = V9 的 TL - 2 = 18, 故 V8 的 TL=18.
- 以此類推求出各點的 TL.

3. 找出TE=TL 的路徑, 即為臨界路徑.