Advanced Graphs · LeetNote

進階圖論涵蓋最短路徑（Dijkstra）、最小生成樹（Prim/Kruskal）、拓撲排序等演算法，用於解決更複雜的圖問題。

Notes:

Dijkstra 適用於非負權重的最短路徑
Bellman-Ford 可處理負權重邊
Prim/Kruskal 用於最小生成樹

拓撲排序（Kahn 入度法）

對有向無環圖 (DAG) 排出「依賴在前、被依賴在後」的線性順序。Kahn 演算法用入度（in-degree）逐步剝除：

fun topoSort(n: Int, edges: Array<IntArray>): IntArray {
    val graph = Array(n) { mutableListOf<Int>() }
    val indeg = IntArray(n)
    for ((u, v) in edges) {            // u -> v
        graph[u].add(v)
        indeg[v]++
    }
    val queue = ArrayDeque<Int>()
    for (i in 0 until n) if (indeg[i] == 0) queue.add(i)  // 無依賴者先入列
    val order = ArrayList<Int>()
    while (queue.isNotEmpty()) {
        val u = queue.removeFirst()
        order.add(u)
        for (v in graph[u]) {
            if (--indeg[v] == 0) queue.add(v)   // 移除 u 後 v 無依賴
        }
    }
    return if (order.size == n) order.toIntArray() else intArrayOf()  // 長度不足代表有環
}

NOTE

排出來的順序長度若小於節點數，代表圖中有環，無法完成拓撲排序——這也是用拓撲排序偵測「課程能否修完」這類環依賴的依據。

Dijkstra 的資料結構

Dijkstra 求非負權重單源最短路，核心是「每次取出當前距離最小的未定點」，所以用最小堆管理候選：

dist[]：起點到各點的目前最短距離，初始除起點外皆無窮大。
最小堆：以 dist 為鍵取出最近的點，鬆弛 (relax) 它的鄰邊。

實作	時間複雜度
最小堆 + 鄰接表	`O((V + E) log V)`
樸素掃描 dist 陣列	`O(V^2)`

稠密圖 V^2 版本反而簡單夠用；稀疏圖用堆較快。負權邊要改用 Bellman-Ford（O(VE)，並能偵測負環）。最小生成樹則用 Prim（類 Dijkstra，堆選最小橫切邊）或 Kruskal（排序所有邊 + Union-Find 避環）。

跨倉庫導讀

對應理論章節：圖