拓撲排序

🎯 什麼情境該想到我

當你「有一堆任務，而且它們之間有先後相依」的時候——建置系統、套件相依、資料庫遷移、CI pipeline、Excel 公式重算、模組初始化順序。
★ 它同時解決兩件事：排出順序 + 偵測循環相依。

⚙️ 怎麼用（兩種演算法與選擇）

定義

對有向無環圖（DAG）排出一個線性順序，使得每條邊 $u \to v$ 都滿足 $u$ 排在 $v$ 前面。

★ 前提：必須是 DAG。有環就不存在拓撲序——而「偵測不出拓撲序」正是偵測循環相依的方法。
拓撲序通常不唯一（沒有相依關係的任務可以任意排）。

演算法一：Kahn（BFS 式，入度法）

// 回傳拓撲序；若有環則 ok = false
func TopoSortKahn(adj [][]int, n int) (order []int, ok bool) {
    indeg := make([]int, n)
    for u := range adj {
        for _, v := range adj[u] { indeg[v]++ }
    }
    q := []int{}
    for u := 0; u < n; u++ {
        if indeg[u] == 0 { q = append(q, u) }   // ★ 沒有前置需求的，先做
    }
    for len(q) > 0 {
        u := q[0]; q = q[1:]
        order = append(order, u)
        for _, v := range adj[u] {
            indeg[v]--
            if indeg[v] == 0 { q = append(q, v) }  // ★ 前置都完成了，可以做了
        }
    }
    // ★ 沒排完 = 剩下的都在環裡
    return order, len(order) == n
}

★ Kahn 的最大優點：q 裡的節點彼此沒有相依，可以「同時做」。
這正是建置系統與 CI 的平行排程做法——每一輪取出的就是「這一批可以並行的任務」。
廣度優先搜尋的層次概念在這裡直接變成「平行批次」。

演算法二：DFS 後序反轉

func TopoSortDFS(adj [][]int, n int) (order []int, ok bool) {
    color := make([]int, n)          // 0白 1灰 2黑，見 [[深度優先搜尋]]
    var dfs func(int) bool
    dfs = func(u int) bool {
        color[u] = 1
        for _, v := range adj[u] {
            if color[v] == 1 { return false }      // ★ 回邊 = 有環
            if color[v] == 0 && !dfs(v) { return false }
        }
        color[u] = 2
        order = append(order, u)     // ★ 後序：所有後代都處理完才加入自己
        return true
    }
    for u := 0; u < n; u++ {
        if color[u] == 0 && !dfs(u) { return nil, false }
    }
    slices.Reverse(order)            // ★ 關鍵：後序完成的逆序就是拓撲序
    return order, true
}

★ 為什麼「後序反轉」是對的：

節點 $u$ 在它所有後代都處理完之後才被加入 order。
所以 order 裡，後代永遠排在祖先前面。反轉之後，祖先就在後代前面——正是拓撲序。

★ 兩者怎麼選

	Kahn（BFS）	DFS 後序
環偵測	排不完就有環，還能指出剩下哪些在環裡	遇到回邊就有環
★ 平行批次	✅ 天然支援（同一輪的可並行）	❌
字典序最小的拓撲序	✅ 把佇列換成二元堆積即可	❌
實作	迭代，不會爆堆疊	遞迴（深圖要改迭代）
建議	★ 實務預設用 Kahn	需要 DFS 的其他資訊時

複雜度

$O (V + E)$ ，空間 $O (V)$ 。

★ 實務應用

場景	說明
建置系統	Make、Bazel、Gradle —— Kahn 的每一輪就是可平行編譯的一批
套件管理	安裝順序；偵測循環相依並報錯
資料庫遷移	migration 的執行順序
★ 模組初始化	Go 的 package 初始化順序就是拓撲序；import cycle 編譯期就被拒絕，正是因為它不是 DAG
Excel / 試算表	公式的重算順序；循環參照的偵測
CI/CD	job 的相依與平行度（見工具-部署管線與持續交付）
課程排課	先修科目

★ 「偵測循環相依」常常比「排出順序」更有價值。
一個報得出「A → B → C → A」的錯誤訊息，比只說「有循環相依」有用得多——
要輸出環的內容，Kahn 排不完時剩下的節點集合就是（或包含）環。

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 有環就沒有拓撲序。程式碼一定要處理 ok == false 的分支，而且錯誤訊息要指出是哪些節點成環。
拓撲序不唯一。不要寫出依賴特定順序的測試——除非你用了字典序最小的版本。
★ 平行執行時要注意「同一輪」的定義：Kahn 的佇列裡的節點可以並行，但要在這一批全部完成後才減下一批的入度，否則會競態。
入度要先算完整再開始。邊加到一半就開始跑會得到錯的結果。
孤立節點（入度出度都是 0）也要納入，否則 len(order) == n 的檢查會誤判。
動態變化的相依圖（邊一直在加）要重新跑，或用增量式拓撲排序（複雜得多）。
最長路徑／關鍵路徑（專案排程的 CPM）是在拓撲序上做 DP——這是 DAG 才能做的事，一般圖的最長路徑是 NP-hard（見 NP 完備性）。

🔗 相關工具

深度優先搜尋 —— DFS 版的基礎與三色標記
廣度優先搜尋 —— Kahn 是它的變形
動態規劃 —— DAG 上的最長路／計數都是在拓撲序上做 DP
併查集 —— 無向圖的連通性（不同問題，常被混淆）
工具-部署管線與持續交付 —— CI 的相依與平行
演算法導論

Quartz 5

Explorer