把一堆有先後相依的事情,排成一條不違反任何順序的直線。排課、編譯、任務排程都靠它。
入度(in-degree) —— 有幾條箭頭「指向」這個節點。入度 0 = 沒有任何先決條件,現在就能做。
1. 入度 0 的先進場 —— 把所有入度 0 的節點丟進佇列。
2. 取一個排出,砍它的出邊 —— 從佇列拿一個放進結果,對它每個下游鄰居入度減 1(它的先決條件少了一個)。
3. 下游入度歸零就進場 —— 某個鄰居入度減到 0,代表它的先決都排好了,加進佇列。
4. 排出數 < 節點數 = 有環 —— 佇列空了卻還有節點沒排出,代表它們卡在環裡(入度永遠歸不了零)。
O(V+E);Kahn 的好處是順便偵測環、也方便控制輸出順序(想要字典序最小就把佇列換成最小堆)。O(V+E)。資料結構要先修程式設計、演算法要先修資料結構。排出一張「照這順序修一定不卡」的課表。
Makefile、npm 裝套件:先把你依賴的東西建好 / 裝好,才輪到你。順序錯就編不過。
先襪子後鞋子、先內衣後外套;但襪子跟內衣誰先都行 —— 所以合法順序不只一種。
節點上方數字是入度(指向它的箭頭數)。每步從佇列(琥珀)取一個排出(紫色正在排出的),砍掉它的出邊、下游入度減 1,減到 0 就進佇列,排出的變綠色。切「有環」情境看 Kahn 怎麼卡住。按「下一步」。
從 Kahn 入度法、偵測環、課程表能不能修完、DFS 後序法,到字典序最小、DAG 最長/最短路、有向圖偵測環、列出所有拓樸序,最後一張應用小結。
❌ 圖有環還想拓樸排序 —— 根本不存在合法順序。務必先確認是 DAG;用 Kahn 時「排出數 < 節點數」就是有環的信號。
❌ 以為答案唯一 —— 平手的節點(同時入度 0)誰先都行,通常有多種合法順序。要固定結果就指定規則(如字典序最小)。
❌ 邊的方向搞反 —— u→v 代表「u 要在 v 前面」(u 是 v 的先決)。方向反了整個順序就反,課程表就變成「先修進階再修基礎」。
❌ DFS 法壓堆疊時機錯 / 忘了反轉 —— 一定要在後序(子孫都處理完)才把自己壓進去,最後整個反轉才是拓樸順序。
把答案打到對話裡,我幫你對。