> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/4-graph/4.5-aov-network.md). # 4.5 - AOV Network Activity-on-Vertex 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) 括號中可交換順序。