4.5 - AOV Network

Activity-on-Vertex Network

AOV Network中， $G=<V,E>$為有向圖:

• V(vertex): 代表工作(Activity)

• E(edge): 代表工作之間的執行順序

  e.g. $i→j:$ 代表 $i$ 必須先於 $j$ 執行

Topological Sort

給定一個不具cycle的AOV Network，則至少可以找出≥1組頂點拜訪順序，此順序滿足:

若$i$有path到$j$，則在此順序中，$i$必定出現在$j$前。

若有cycles，則沒有topological sort。

• 求法:

1. 先找出in-degree = 0的頂點

2. 輸出此頂點，並將此頂點與其out-edge刪除

3. 重複以上步驟，直到沒有頂點，或找不到in-degree = 0的頂點

4. 若仍有剩餘的頂點代表此圖沒有topological sort

e.g.

Topological Sort: 1 (2, 3, 4) (5, 6) 括號中可交換順序。