Graph 演算法｜拓撲排序法 (Topological Sorting with Kahn's Algorithm)
目錄
節錄自 CK 技術週報 #5，對此內容有興趣歡迎免費訂閱電子報，每週三持續更新中。
嗨嗨 👋 大家，歡迎閱讀第 5 期的 CK 技術週報，新年開工該收心回來寫週報了。
在這個連假中，我盡可能地遠離社群媒體，在返鄉高鐵上把《做自己的生命設計師》給看完了，啟發滿滿之外在想今年說不定可以養成至少一個月讀一本書的習慣。另外也難得地陪家人聊天走春、去朋友家打了一整夜的電動、刮了幾張沒中獎的刮刮樂等等。
不知道大家有沒有趁春節連假完成了什麼拖延已久的計劃或開始什麼新習慣，歡迎留言一同交流！
好好放鬆休息之外，從年初開始的刷題習慣也希望繼續延續下去，因此即使是過年假期抓到空檔也會至少小刷一個 easy 練練手，體感好像持續每天打卡個 20 幾天後就會越過排斥的那道坎，開始體會到所謂刷題是一種遊戲的感覺，看著 Rank 與 AC 數的提升漸漸就會有好像在進步的感覺。
有點扯遠了，回到正題最近在寫幾間公司的前測時，意外地一直遇到 Graph 中 Topological Sorting 相關的問題，個人感覺這個演算法基本上是個沒耐著性子理解過，就只能用暴力解去寫出勉強能通過幾個測資的 TLE (Time Limit Exceeded) 程式，於是這篇就來試著由淺入深來學習並筆記一下。
在此題型的經典題「大學修課擋修 (Course Schedule)」的討論區中找到 WilliamFiset 的這個教學影片（連結），覺得講解得很不錯，以下就搭配著其中的圖解輔助說明。
🧥 如何決定出門前的穿衣順序？
假設你今天起床，有 6 件衣服需要去按順序穿上，那你該如何決定穿的順序？
因為你不可能「先穿鞋才穿襪子」或做出「內褲外穿」的舉動，所以我們可以把規定好的穿衣順序抽象化成一個有向圖的關係，每個「要做的事 (頂點)」間會有「先後關係 (有向箭頭)」，用箭頭來表示一定要先做 A 才能做 B。
先不扯到程式要怎麼實作的話，我們可以透過人工的方式想出其中一組解如上圖，可以用「襪子、衣服、帽 T、內褲、褲子、鞋子」這樣的順序來穿完這 6 件衣服，就可以順利出門了。你可能會注意到這類的問題通常不只唯一解，這也是此種題型的一個特性之一，通常比較基本的題型會問「是否有解」或「求出其中一組解」。
在現實世界中，有許多問題可以被抽象化為有向圖的方式來表示「在做 A 之前應該先做 B」，像是：
- 大學課程擋修規則
- 程式部署流程
- 事件排程
而要找出這類問題的執行順序的解，就可以用上今天的主角 — 拓撲排序法，在解釋這個演算法前，會有一個前導知識是 DAG，這裡先來複習下這個資料結構。
🕸️ 有向無環圖 (DAG，Directed Acyclic Graph)
在資料結構中，圖 (Graph) 指的不是圖片，是一種用來表示關聯的結構，由頂點 (Vertex) 與邊 (Edge) 組成。
而有向無環圖 (Directed Acyclic Graph，簡稱 DAG) 這樣的結構，顧名思義就是這個圖「有向」且「無環」，也就是頂點間的邊具有方向性 (有箭頭)，且在圖中不會有環的結構。
實際舉個例子，可以暫停在下面這張圖依照這個定義來練習判斷看看以下哪些是 DAG：
公佈答案！
從下圖可以看到，2 的邊沒有箭頭、4 與 5 圖上有環，因此這些都不是 DAG：
那為什麼在理解拓撲排序法前要知道 DAG 的概念呢？因為拓撲排序法是想要再有向圖中去找到一組可行的解。參考下圖的例子來看看，在有環圖中要去找走完每個頂點的解法時，會發現有些點彼此依賴另一個點為前置條件，因此最後會無法決定誰先做而卡住。
🎯 拓撲排序法
理解了 DAG 後，接著就來了解下什麼是拓撲排序法。
拓撲排序法是指在一個有向無環圖 (DAG) 中去決定這些點能夠以什麼樣順序依序觸發的演算法。而其中 Kahn's Algorithm 是一種相對常見且簡單理解的實現，它是拓撲排序法的 BFS 實作方式，可以在 O(V + E) 的時間複雜度內完成 (其中 V 代表圖的頂點數、E 代表邊數)。
以下就實際用個例子走過 Kahn's Algorithm 的思路。
📝 Kahn's Algorithm
如上圖，假如今天有 A、B、C、D 四門課程，在修每門課程前有些會有擋修的限制，或稱為前置條件 (prerequisite)：
- A：無擋修
- B：需先修完 A、C
- C：需先修完 A
- D：需先修完 B、C
今天如果直接人工從圖上去判斷的話會知道可以用 A → C → B → D 這樣的方式來修課就能順利修完所有課程，那如果使用演算法時該怎麼去理解呢？
在 Kahn’s Algorithm 中，最重要的兩個概念是：
- in-degree (入度)：指向該節點的箭頭數量 (the number of incoming edges)
- out-degree (出度)：從該節點出發的箭頭數量 (the number of outgoing edges)
算出每個點的入度，並用一個 queue 來推入入度為 0 的頂點
以上面這個圖為例，我們可以用以下步驟去找到修課順序：
- 先找出每個頂點的入度 (圖上藍字)：
- A：0
- B：2
- C：1
- D：2
- 另外用一個 queue 來推入入度為 0 的頂點，因此把 A 加入 queue，而其他節點不為 0 所以暫時不理會
- 算完要放入 queue 的節點後，就可以從 queue 取出第一個可以修的課程 A，把它移除並標記為已完成 (參考下圖)
- 接下來去檢查剩下的課程，如果有以 A 為前置的就把對應的入度都減 1，因為目前依賴關係已經不存在了
- 減完後，現在變成 C 的入度為 0，就可以反覆執行上面 2~4 的步驟
檢查剩下的課程，如果有以 A 為前置的就把對應的入度都減 1
反覆執行直到 queue 為空後就能確認是否有解 (可以去判斷最後得到的解長度是否與課程數相等)，並在有解時得到其中一組解。
在有環圖中套用此演算法找不到解
假如今天改成像上面的圖，會注意到 A → C → B 形成一個環，此時如果去計算每個點的入度，會發現沒人是 0，因此無解。
另外從這個例子也可以發現要檢查該圖是否為有環圖 (cyclic graph)，拓撲排序法也是個有效的方式。
實例：Course Schedule
理解了原理後，可以再實際用 LeetCode 上的拓撲排序經典題 — 207. Course Schedule 練練手，因為篇幅限制這部份筆記可以再參考這篇筆記。
