Graphs · LeetNote

圖由頂點 (Vertex) 和邊 (Edge) 組成，用來表示物件之間的關係。BFS 和 DFS 是最基本的圖遍歷演算法。

Notes:

圖的表示方式：鄰接矩陣 vs 鄰接表
BFS 適合最短路徑（無權圖），DFS 適合連通性和路徑探索
Union-Find 適合處理動態連通性問題
拓撲排序用於有向無環圖 (DAG) 的依賴關係

兩種表示法

表示法	空間	查「u→v 是否相鄰」	適合
鄰接矩陣	`O(V^2)`	`O(1)`	稠密圖、頻繁查邊
鄰接表	`O(V + E)`	`O(deg)`	稀疏圖（多數題目）

NOTE

鄰接表本質上就是「稀疏矩陣的壓縮」：真實世界的圖大多稀疏（邊遠少於 V^2），只存實際存在的邊能省下大量空間，這也是大規模圖（社群網路、網頁連結）唯一可行的存法。

DFS 與 BFS 模板

兩者時間都是 O(V + E)、空間 O(V)，差別在用 stack（遞迴）還是 queue，以及探索順序。

// DFS：遞迴，適合連通分量、路徑探索、偵測環
fun dfs(u: Int, graph: List<List<Int>>, visited: BooleanArray) {
    visited[u] = true
    for (v in graph[u]) {
        if (!visited[v]) dfs(v, graph, visited)
    }
}

// BFS：佇列，適合無權圖最短路、逐層擴散
fun bfs(start: Int, graph: List<List<Int>>): IntArray {
    val dist = IntArray(graph.size) { -1 }
    val queue = ArrayDeque<Int>()
    dist[start] = 0
    queue.add(start)
    while (queue.isNotEmpty()) {
        val u = queue.removeFirst()
        for (v in graph[u]) {
            if (dist[v] == -1) {          // 未訪問
                dist[v] = dist[u] + 1
                queue.add(v)
            }
        }
    }
    return dist
}

IMPORTANT

圖題務必維護 visited，否則有環時會無限繞圈。網格題（島嶼類）可把每個格子視為節點、上下左右為邊，套同一套 BFS/DFS。

圖的屬性

動手前先確認：有向 / 無向、加權 / 無權、是否可能有環、是否連通。這些屬性決定該用哪種演算法——例如無權最短路用 BFS，加權非負用 Dijkstra，有負權用 Bellman-Ford（見 Advanced Graphs）。

跨倉庫導讀

對應理論章節：圖