# 4.5 - AOV Network AOV Network中， $$G=\$$為有向圖: * 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) 括號中可交換順序。