拓樸排序 - HackMD

# 拓樸排序 > 上一篇文章　[DFS/BFS題目介紹](https://hackmd.io/_4BYmPUwSkefbBAYjLvoYw) > 下一篇文章　[Euler路徑與Euler圖](/UGAvs7XoTTqzLJ2UM2a3kA) > 先備知識　　無 > 延伸閱讀　　無 --- ## 概述 拓樸排序(Topological sorting)為針對有向(Directed Graph)且沒有定向環而制定的排序方式，無法使用在其他類型的圖，應用在任務編排順序，頂點(Node)為要執行的任務，而邊(Edge)表示執行任務的條件，需要先完成前面的任務才可以執行後面的任務。 ## 條件 > :::success > - 有向圖。 > - 序列中包含所有頂點，且每個頂點只會出現一次。 > - 如果頂點A的序位在頂點B之前，則圖中只存在A到B的邊，B到A不存在。 > ::: > :::danger > - 無向圖。 > - 序列裡的頂點有缺少或重複出現。 > - 出現了定向的環，或者是其中有兩個頂點具有雙向的邊。 > ::: ## 範例 拓樸排序的解鎖機制以遊戲《鋼鐵雄心4》（Hearts of Iron IV）為例，在遊戲中的國策系統可以根據不同打法或者是當下需求選擇不同的發展方向，玩家需要完成某些前置國策才可以繼續往下發展，這些前置的國策可能會有很多個也有可能只有一個，一個國策也可以導向許多不同的分支，然而，這些國策有著不可回朔的性質，這與拓樸排序的沒有定向環相同。國策樹： ![example](https://hackmd.io/_uploads/ryI8HPu61x.png) 拓樸排序範例： ![messy_graph](https://hackmd.io/_uploads/H18AuPOpJe.svg) ## 拓樸排序介紹 ### 目標拓樸排序的目標為針對一個有向且沒有定向環的圖制定一個正確的順序，但根據不同方法可能會有多種可能。 ### 輸入/輸出 - 輸入一張符合拓樸排序要求的有向圖 - 輸出為一個陣列，紀錄頂點的順序 ## Kahn's algorithm 此演算法的核心為根據入度`deg(v)`來判斷當下可執行之任務，有點像BFS的方式。 ### 判斷當下可以執行什麼任務 >當`deg(v) = 0`時，代表當前沒有任何頂點在它的前方，以起始點為例，因為>起點之前不會有任何任務，所以起始點的入度為0(`deg(v) = 0`)。 >> 範例程式碼 >> ```python=4 >> in_degree = [0] * n >> for u in range(n): >> for v in graph[u]: >> in_degree[v] += 1 >> ``` >:::spoiler 註解（點我展開） >`n`代表頂點數量。 >`in_degree[v]`為節點`v`的入度。 >`graph[u]`為`u`指向的頂點列表。 >::: ### 走訪每個入度為零的頂點 >接續上面所述，因為`deg(v) = 0`，代表是可執行的，跟`BFS`的原理相似，>將它們加入`queue`後一一開始走訪。 >將所有`deg(v) = 0`的頂點加入`queue`: >> 範例程式碼 >> ```python=9 >> queue = deque([i for i in range(n) if in_degree[i] == 0]) >> ``` >從`queue`將這些頂點一一取出加入陣列中: >> 範例程式碼 >> ```python=12 >> while queue: >> u = queue.popleft() >> topo_order.append(u) >> ``` >:::spoiler 註解（點我展開） >`topt_order`是結果陣列。 >::: ### 更新每個節點的狀態 >拜訪完頂點後，我們需要將該頂點後面的所有頂點的入度減一表示前置頂點(之一)已拜訪完成，計算後如果入度為零就可以加入`queue`以進行下一次的拜訪了。 >> 範例程式碼 >> ```python=16 >> for v in graph[u]: >> in_degree[v] -= 1 >> if in_degree[v] == 0: >> queue.append(v) >> ``` ### 返回結果陣列將所有頂點都加入結過陣列後就可以回傳了。 > 範例程式碼 > ```python=21 > return topo_order > ``` ### 完整程式碼 ```python= from collections import deque def kahn_topological_sort(graph, n): in_degree = [0] * n for u in range(n): for v in graph[u]: in_degree[v] += 1 queue = deque([i for i in range(n) if in_degree[i] == 0]) topo_order = [] while queue: u = queue.popleft() topo_order.append(u) for v in graph[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) return topo_order ``` ## DFS 透過遞迴`DFS`遍歷圖，當某個頂點後的所有頂點皆被訪問後，再把他們全部放進結果陣列中。 ### 建立一個訪問標記陣列 >建立一個訪問陣列在`DFS`遞迴在走訪過程中加入並判斷那些頂點已經被訪問過。 >訪問陣列： >> 範例程式碼 >> ```python=2 >> visited = [False] * n >> ``` >結果陣列： >> 範例程式碼 >> ```python=3 >> stack = [] >> ``` >:::spoiler 註解（點我展開）> >使用`stack`來記錄反向的拓樸排序結果。 >::: ### 進行DFS >使用`DFS`來找出該頂點後的所有頂點，並且檢查是否訪問過，如果沒有訪問過則>逐一將訪問陣列改成`True`，表示已訪問過，全部找到後才將該頂點加入>`stack`。 >> 範例程式碼 >> ```python=5 >> def dfs(u): >> visited[u] = True >> for v in graph[u]: >> if not visited[v]: >> dfs(v) >> stack.append(u) >> ``` ### 檢查整張圖 >在某些情況中，可能會有某些部分是不連通的，我們需要把它們找出來並且再進行一次`DFS`，以確保每個頂點都被訪問過。 >> 範例程式碼 >> ```python=12 >> for i in range(n): >> if not visited[i]: >> dfs(i) >> >> ``` ### 得到拓樸排序 >在進行完上述的步驟後，此時`stack`中的順序還不是正確的順序，我們需要把>整個`stack`反轉過來才是正確的順序。 >> 範例程式碼 >> ```python=16 >> return stack[::-1] >> ``` ## 完整程式碼 ```python= def dfs_topological_sort(graph, n): visited = [False] * n stack = [] def dfs(u): visited[u] = True for v in graph[u]: if not visited[v]: dfs(v) stack.append(u) # 所有鄰接點都處理完後再加入 for i in range(n): if not visited[i]: dfs(i) return stack[::-1] # 反轉堆疊即為拓樸排序結果 ``` --- > 上一篇文章　[DFS/BFS題目介紹](https://hackmd.io/_4BYmPUwSkefbBAYjLvoYw) > 下一篇文章　[Euler路徑與Euler圖](/UGAvs7XoTTqzLJ2UM2a3kA) > 先備知識　　無 > 延伸閱讀　　無