廣度優先搜尋

🎯 什麼情境該想到我

當你「要找最少步數」的時候——最少換乘、最少操作次數、社交網路的幾度關係、迷宮最短路。
★ 只要邊權相同（或無權），BFS 就是最短路演算法——比 Dijkstra 最短路徑 簡單也快得多。

⚙️ 怎麼用（機制與正確性）

運作機制：用佇列，一層一層往外擴

起點 s
 ├─ 距離 1 的所有點      ← 全部走完，才進入下一層
 ├─ 距離 2 的所有點
 └─ 距離 3 的所有點 ⋯

func BFS(adj [][]int, s int) []int {
    dist := make([]int, len(adj))
    for i := range dist { dist[i] = -1 }
    dist[s] = 0
    q := []int{s}                       // 見 [[堆疊與佇列]]：長壽命佇列要用環形緩衝
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        for _, v := range adj[u] {
            if dist[v] == -1 {          // ★ 入隊時就標記，不是出隊時
                dist[v] = dist[u] + 1
                q = append(q, v)
            }
        }
    }
    return dist
}

★ 「入隊時標記」是最常見的 bug 來源。
如果改成出隊時才標記，同一個節點會被重複放進佇列很多次——
在稠密圖上會從 $O(V+E)$ 退化成指數級。

★ 為什麼 BFS 保證最短（歸納證明）

不變式：佇列中的節點距離最多相差 1，且是非遞減的。

歸納：

• 起點距離 0，佇列 = [s]，成立
• 從佇列取出距離 $d$ 的節點 $u$，它的鄰居若未訪問則距離為 $d+1$，放到佇列尾端
• → 佇列裡永遠是 $[d,d,\dots ,d,d+1,\dots ,d+1]$

所以節點是「按距離遞增的順序」被發現的——
第一次到達某個節點時，走的必定是最短路（否則它會在更早的某一層就被發現）。

★ 這個保證只在「所有邊權相同」時成立。
邊權不同時，「先到達」不代表「最短」——那就需要 Dijkstra 最短路徑 的優先佇列。

複雜度

時間	$O(V+E)$ —— 每個節點入隊一次、每條邊檢查一次
空間	$O(V)$ —— ★ 最差情況佇列裡有一整層的節點

三個重要變體

變體	做什麼	收益
多源 BFS	一開始把所有起點都放進佇列（距離都是 0）	★ 一次 BFS 算出「到最近的任一起點」的距離。 例：地圖上每一格到最近的醫院。比對每個起點各跑一次 BFS 快 $k$ 倍
★ 雙向 BFS	從起點和終點同時往中間搜，相遇就停	分支因子 $b$、距離 $d$ 時，從 $O(b^d)$ 降到 $O(b^{d/2})$——這是平方根級的改善。 用在「六度分隔」「字梯」這類大搜尋空間
0-1 BFS	邊權只有 0 和 1 時，用雙端佇列：權 0 放前面、權 1 放後面	$O(V+E)$ 解決，不需要 Dijkstra 的 $O(E\log V)$

BFS vs DFS

	BFS	深度優先搜尋
結構	佇列（FIFO）	堆疊（LIFO）或遞迴
順序	一層一層	一條路走到底再回頭
最短路（無權）	✅ 保證	❌ 不保證
空間	$O(\text{最寬那層})$	$O(\text{最深深度})$
適合	最短路、層次遍歷、最近的目標	環偵測、拓撲排序、連通分量、回溯

★ 程式碼幾乎一樣，只差「用佇列還是堆疊」——但性質完全不同（見 堆疊與佇列）。

🧪 我實際套用的紀錄

• （待填）

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

• ★ 邊權不同就不能用（會得到錯的「最短」路）→ 用 Dijkstra 最短路徑；有負權用 Bellman-Ford 最短路徑。
• ★ 空間可能爆炸。在分支因子大的圖上（如遊戲狀態空間），「最寬的那一層」可能有天文數字個節點。
  → 對策：雙向 BFS、迭代加深 DFS（IDDFS，空間 $O(d)$）、A*（有啟發函式時）。
• Go 的 slice 佇列會洩漏底層陣列（q = q[1:]）。長時間執行或大圖上要用環形緩衝（見 堆疊與佇列）。
• 要輸出路徑不只是距離時，要另外記 parent[] 再回溯。
• 隱式圖（狀態空間搜尋）要記得去重，否則會重複展開同一個狀態——用 雜湊表 存已訪問狀態。
• 無權圖上不要用 Dijkstra。能用 BFS 就用 BFS：$O(V+E)$ vs $O(E\log V)$，而且沒有堆的常數開銷。

🔗 相關工具

• 深度優先搜尋 —— 對照組，差別只在資料結構
• 堆疊與佇列 —— BFS 的佇列該怎麼實作
• Dijkstra 最短路徑 —— 邊權不同時的推廣（BFS 是它的特例）
• 拓撲排序 —— Kahn 演算法就是 BFS 的變形
• 演算法導論