拓撲排序 (Topological Sort)#

什麼是拓撲排序？#

將有向無環圖 (DAG) 的頂點排成線性序列，使得所有邊 (u, v) 中，u 都排在 v 之前。

生活範例：穿衣順序#

flowchart LR
    內褲 --> 外褲
    外褲 --> 腰帶
    上衣 --> 腰帶
    腰帶 --> 外套
    襪子 --> 鞋子

    style 內褲 fill:#e3f2fd
    style 襪子 fill:#e3f2fd
    style 上衣 fill:#e3f2fd
    style 外套 fill:#e8f5e9
    style 鞋子 fill:#e8f5e9

有效的拓撲序列：內褲 ➡️ 襪子 ➡️ 上衣 ➡️ 外褲 ➡️ 鞋子 ➡️ 腰帶 ➡️ 外套

拓撲排序的結果不唯一，只要滿足所有依賴關係即可。

應用場景#

場景	說明
編譯依賴	確定源檔案的編譯順序
課程先修	安排課程學習順序
任務調度	確定任務執行順序
環檢測	判斷有向圖是否有環

Kahn 演算法（BFS）#

核心思想#

不斷找出入度為 0 的頂點（無依賴），輸出並移除。

演算法步驟#

flowchart TD
    A[1. 計算所有頂點入度] --> B[2. 入度=0 的頂點入隊]
    B --> C{佇列為空?}
    C -->|否| D[3. 取出頂點並輸出]
    D --> E[4. 相鄰頂點入度 -1]
    E --> F{入度變為 0?}
    F -->|是| G[加入佇列]
    F -->|否| C
    G --> C
    C -->|是| H{輸出數 = 頂點數?}
    H -->|是| I[拓撲排序完成]
    H -->|否| J[存在環！]

    style I fill:#e8f5e9
    style J fill:#ffebee

計算所有頂點的入度
將入度為 0 的頂點加入佇列
取出佇列頂點，輸出，將其相鄰頂點入度 -1
若有新的入度為 0 的頂點，加入佇列
重複直到佇列為空

Kahn 演算法程式碼

fun topologicalSortKahn(n: Int, edges: Array<IntArray>): List<Int> {
    // 建圖 + 計算入度
    val graph = Array(n) { mutableListOf<Int>() }
    val inDegree = IntArray(n)

    for ((u, v) in edges) {  // u → v
        graph[u].add(v)
        inDegree[v]++
    }

    // 入度為 0 的頂點入隊
    val queue = ArrayDeque<Int>()
    for (i in 0 until n) {
        if (inDegree[i] == 0) queue.add(i)
    }
    val result = mutableListOf<Int>()

    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        result.add(node)

        for (neighbor in graph[node]) {
            inDegree[neighbor]--
            if (inDegree[neighbor] == 0) {
                queue.add(neighbor)
            }
        }
    }

    // 檢測環：若輸出數量不等於頂點數，說明有環
    return if (result.size == n) result else emptyList()
}

DFS 演算法#

核心思想#

後序走訪的逆序即為拓撲排序。

演算法步驟#

對每個未訪問的頂點執行 DFS
遞迴訪問所有依賴的頂點
回溯時將當前頂點加入結果（後序）
最後反轉結果

DFS 演算法程式碼

fun topologicalSortDfs(n: Int, edges: Array<IntArray>): List<Int> {
    // 建立逆鄰接串列（指向依賴的頂點）
    val graph = Array(n) { mutableListOf<Int>() }
    for ((u, v) in edges) {  // u → v（v 依賴 u）
        graph[v].add(u)  // 逆向：v 需要先完成 u
    }

    val visited = BooleanArray(n)
    val result = mutableListOf<Int>()

    fun dfs(node: Int) {
        if (visited[node]) return
        visited[node] = true

        for (dep in graph[node]) {
            dfs(dep)
        }

        result.add(node)  // 後序：依賴都處理完才輸出自己
    }

    for (i in 0 until n) {
        dfs(i)
    }

    return result  // 已經是正確順序（使用逆鄰接串列）
}

複雜度分析#

演算法	時間複雜度	空間複雜度
Kahn	`O(V + E)`	`O(V)`
DFS	`O(V + E)`	`O(V)`

環檢測#

有環 = 無法拓撲排序

Kahn 演算法檢測#

若最終輸出的頂點數 < 總頂點數，說明有環。

DFS 檢測#

維護三種狀態：未訪問、訪問中、已完成

若訪問到「訪問中」的頂點，說明有環

fun hasCycle(n: Int, edges: Array<IntArray>): Boolean {
    val UNVISITED = 0
    val VISITING = 1
    val VISITED = 2
    val state = IntArray(n)  // 預設全為 UNVISITED (0)
    val graph = Array(n) { mutableListOf<Int>() }

    for ((u, v) in edges) {
        graph[u].add(v)
    }

    fun dfs(node: Int): Boolean {
        if (state[node] == VISITING) return true  // 發現環
        if (state[node] == VISITED) return false

        state[node] = VISITING
        for (neighbor in graph[node]) {
            if (dfs(neighbor)) return true
        }
        state[node] = VISITED
        return false
    }

    return (0 until n).any { state[it] == UNVISITED && dfs(it) }
}