資料結構之 【拓撲排序】

拓撲排序的概念

一個無環的有向圖稱為無環圖（Directed Acyclic Graph），簡稱DAG圖。

所有工程或者某種流程都可以分為若幹個小的工程或者階段，我們稱這些小的工程或階段為“活動”。

在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優先關系，這樣的有向圖為頂點表示活動的網，我們稱之為AOV網（Active On Vertex Network），AOV網不能存在回路。

拓撲序列：設G=(V,E)是一個具有n個頂點的有向圖，V中的頂點序列V1，V2，....，Vn滿足若從頂點Vi到Vj有一條路徑，則在頂點序列中頂點Vi必在頂點Vj之前。則我們稱這樣的頂點序列為一個拓撲序列。

拓撲排序：所謂的拓撲排序，其實就是對一個有向圖構造拓撲序列的過程。

拓撲排序算法：

對AOV網進行拓撲排序的方法和步驟如下：

1. 從AOV網中選擇一個沒有前驅的頂點（該頂點的入度為0）并且輸出它；
2. 從網中删去該頂點，并且删去從該頂點出發的全部有向邊；
3. 重複上述兩步，知道剩餘網中不再存在沒有前去的頂點為止。

因為需要删除頂點，是以選擇鄰接表資料結構表示會更加友善

關鍵路徑

AOE網：在一個表示工程的帶權有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權值表示活動的持續時間，這種有向圖的邊表示活動的網，我們稱之為AOE網（Activity On Edge Network）。

AOE網中沒有入邊的頂點稱為始點或源點，沒有出邊的頂點稱為終點或彙點。

• etv（earliest time of Vertex）：事件最早發生時間
• ltv （latest time of Vertex）：事件最晚發生時間
• ete（earliest time of Edge）：活動最早開工時間
• ete（latest Time of Edge）：活動最晚開工時間

ete和lte相等，就是關鍵路徑，關鍵路徑上的頂點就是關鍵活動。

先進行拓撲排序，

再找關鍵路徑