BFS 與 DFS#

核心差異#

flowchart TB
    subgraph BFS["BFS 廣度優先：層層推進"]
        direction LR
        B1((1)) --> B2((2))
        B1 --> B3((3))
        B1 --> B4((4))
        B2 --> B5((5))
        B2 --> B6((6))
    end

    subgraph DFS["DFS 深度優先：一路到底"]
        direction TB
        D1((1)) --> D2((2))
        D2 --> D5((5))
        D5 --> D6((6))
        D2 -.-> D3((3))
        D1 -.-> D4((4))
    end
特性BFS（廣度優先）DFS（深度優先）
策略層層推進（地毯式）一路到底（鑽研式）
資料結構佇列 (Queue)堆疊 (Stack) / 遞迴
最短路徑保證最短（無權圖）不保證
實作方式迭代遞迴（推薦）或迭代

BFS 廣度優先搜尋#

核心概念#

從起點開始，先訪問所有距離為 1 的節點，再訪問距離為 2 的節點…

     1
   / | \
  2  3  4
 /\    / \
5  6  7   8

訪問順序：1 ➡️ 2,3,4 ➡️ 5,6,7,8

模板程式碼#

fun bfs(start: Int) {
    val queue = ArrayDeque<Int>()
    queue.add(start)
    val visited = hashSetOf(start)

    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        // 處理當前節點

        for (neighbor in getNeighbors(node)) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.add(neighbor)
            }
        }
    }
}

關鍵：將節點加入佇列時立即標記 visited，避免重複入隊。

階層走訪技巧#

while (queue.isNotEmpty()) {
    val levelSize = queue.size  // 鎖定當前層數量
    repeat(levelSize) {
        val node = queue.removeFirst()
        // 處理當前層節點
    }
}

DFS 深度優先搜尋#

核心概念#

選定一條路走到底，無路可走時回溯。

     1
   / | \
  2  3  4
 /\
5  6

訪問順序：1 ➡️ 2 ➡️ 5 ➡️ 6 ➡️ 3 ➡️ 4（遞迴自然形成的順序）

遞迴模板（推薦）#

fun dfs(node: Int, visited: MutableSet<Int>) {
    if (node in visited) return
    visited.add(node)

    // 處理當前節點

    for (neighbor in getNeighbors(node)) {
        dfs(neighbor, visited)
    }
}

迭代模板#

fun dfsIterative(start: Int) {
    val stack = ArrayDeque<Int>()
    stack.addLast(start)
    val visited = mutableSetOf<Int>()

    while (stack.isNotEmpty()) {
        val node = stack.removeLast()
        if (node in visited) continue
        visited.add(node)

        // 處理當前節點

        for (neighbor in getNeighbors(node)) {
            if (neighbor !in visited) {
                stack.addLast(neighbor)
            }
        }
    }
}

建議：面試時優先使用遞迴寫法，程式碼更簡潔，遞迴堆疊自動維護狀態。

樹 vs 圖的處理差異#

結構是否需要 visited
樹通常不需要（無環）
圖必須（可能有環）

圖的搜尋必須維護 visited 集合！否則會陷入無限迴圈。

為什麼圖的遍歷一定要 visited 集合#

前面模板裡到處都看到 visited，這不是寫法習慣，而是數學上的必要。

樹是一種特殊的圖：它沒有環。從根往下走，永遠不會繞回已經走過的節點，所以走訪不必記錄誰來過——反正不會回頭。

但一般的圖可能有環。一旦存在環，若不記錄「已造訪」的節點，遍歷走到環上時就會沿著環一圈又一圈地繞，永遠不會停下：

flowchart LR
    A((A)) --> B((B))
    B --> C((C))
    C --> A

走 A ➡️ B ➡️ C ➡️ A ➡️ B ➡️ C ➡️ …，無限重複。

本質差異：圖有環、樹無環。 正因為圖可能成環，圖的 BFS / DFS 必須額外維護一個 visited 集合（雜湊表或布林陣列）來記下走過的節點，每個節點只處理一次，遍歷才會終止。這是「圖的遍歷」與「樹的遍歷」最根本的不同。

求兩點間的最短路徑時，普通 BFS 從起點像水波一樣往外擴。設分支因子為 k、起終點距離為 d，要搜尋的節點數量大約是 O(kᵈ)——隨距離指數成長。

雙向 BFS 的想法：同時從起點和終點兩邊一起做 BFS，當兩邊的搜尋前緣在中間相遇時，就拼出一條完整最短路徑。

flowchart LR
    S((起點)) -->|前進 d/2| M((相遇點))
    T((終點)) -->|前進 d/2| M

兩邊各只需要走約一半的距離，於是節點數量從 O(kᵈ) 降到約 2 × O(k^(d/2)) = O(k^(d/2))。

方式搜尋規模直覺
單向 BFSO(kᵈ)一個大圓往外擴
雙向 BFSO(k^(d/2))兩個小圓在中間碰頭

距離越遠，差距越誇張：這是指數級的加速。代價是要同時維護兩個搜尋前緣、並在每一步檢查兩邊是否相遇，實作較複雜，且通常要求終點明確、邊可雙向走。

DFS 會產生生成樹 / 生成森林#

DFS 走訪一張圖時，把「實際走過、用來首次抵達某節點」的那些邊挑出來，這些邊會構成一棵生成樹（spanning tree）：它涵蓋所有節點，但只保留圖中的一部分邊（被環跳過、或通往已造訪節點的邊就不算在內）。

如果圖不是連通的，一次 DFS 走不完所有節點，需要對每個尚未造訪的節點各起一次 DFS，於是得到的是多棵生成樹的集合——稱為生成森林（spanning forest），每棵樹對應一個連通分量。

flowchart TB
    subgraph 連通圖["連通圖 → 一棵生成樹"]
        A((1)) --> B((2))
        A --> C((3))
        B --> D((4))
    end
    subgraph 非連通["非連通圖 → 生成森林"]
        E((5)) --> F((6))
        G((7)) --> H((8))
    end

這個概念是後續理解連通分量、橋與割點等課題的基礎。

應用場景#

場景適用演算法
最短路徑（無權）BFS
連通分量BFS 或 DFS
拓撲排序DFS（或 Kahn）
迷宮問題BFS（最短）或 DFS
島嶼數量DFS（常用）
社交網路的 N 度好友

問題：找出某使用者的三度好友（好友的好友的好友）

解法：BFS 是最佳選擇

  • 第 1 層：一度好友
  • 第 2 層：二度好友
  • 第 3 層：三度好友

使用階層走訪技巧，控制搜尋深度即可。

真實應用：網路爬蟲就是圖的遍歷#

整個網際網路其實就是一張巨大的圖：每個網頁是一個節點，每條超連結是一條有向邊。搜尋引擎的爬蟲（crawler / spider）從一批「種子網址」出發，抓下網頁、解析出頁面裡的所有連結，再順著這些連結走到下一批網頁——這正是 BFS / DFS 自動走遍整張圖的過程。爬下來的這張圖結構，也正是 PageRank 計算網頁重要性的輸入。

換句話說，本頁那 10 行的遍歷模板，就是一隻爬蟲的靈魂。但要讓它在真實互聯網上跑起來，工程上的落差是巨大的：

  • 它是有向圖，而且非強連通：A 連到 B 不代表 B 連回 A；有些頁面只進不出、有些孤島根本連不到，單一種子未必走得遍全網。
  • 節點數量近乎無限、需要動態發現：你拿不到一份「所有網頁清單」，節點是邊抓邊解析、邊走邊長出來的。
  • 圖一直在變：網頁會新增、刪除、改內容，連結也持續變動，爬蟲必須反覆回訪，圖永遠抓不「完」。
  • 規模需要大規模並行：要在合理時間內覆蓋數百億頁面，得用上萬台機器並行抓取，於是 visited 集合（去重）、佇列、頻率控制全都變成分散式系統問題。

「教科書 100 行的遍歷」和「工程上能真正跑的爬蟲」之間，差的不是演算法本身，而是規模、動態性與分散式。演算法是骨架，工程才是讓它在真實世界站起來的血肉。

兩個常見誤解：

  1. BFS 不是遞迴。BFS 靠的是佇列 (queue) 主動管理待訪節點，並非依賴函式呼叫堆疊；會用到呼叫堆疊（遞迴）的是 DFS。把 BFS 寫成遞迴，反而是逆著它的本質。
  2. 找「最少步數 / 最短（無權）路徑」要用 BFS，不是 DFS。BFS 層層推進，第一次抵達目標時的層數就是最短距離；DFS 一路鑽到底，先找到的路徑往往不是最短的。
Backward 圖的基礎 島嶼問題 Forward