BFS 廣度優先搜尋教學

學習目標

了解 BFS 的核心直覺（分層擴張 / 一圈圈向外）。
能寫出 標準 BFS（佇列）並標記層級（dist）。
會用 BFS 解 無權圖最短路徑、判二分圖。
理解與 DFS 的差異與何時選 BFS、何時選 DFS。

先備知識 & 圖的表示法

基本概念

圖：頂點 V、邊 E，可分無向 / 有向。
visited：避免重複拜訪、避免死循環。
dist / level：記錄「從起點走到這個點的步數」。
多連通分量：圖可能不是一整塊，要對所有未訪點啟動 BFS。

圖的表示法

鄰接表（推薦）：節省空間，適合稀疏圖。
鄰接矩陣：適合點數不大、邊多到接近滿圖。
稀疏圖 → 用鄰接表；你現場教學也好講。

// 鄰接表示意（C++）
int n, m;
vector adj[100005];
for (int i=0;i> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a); // 無向圖
}

核心概念（直覺）

起點入佇列（queue），dist=0。
反覆：佇列彈出一個點 u，把所有「尚未訪問的鄰居」v 入佇列。
以層級擴張：先被放進佇列的，一定比較靠近起點 → 無權圖最短路徑。
「同層」的輸出順序會受鄰居的順序影響，但最短距離不會變。
若希望評測穩定，可先對鄰居排序，再入佇列。

適用情境與應用

無權圖最短路徑：迷宮、棋盤走路、最少步數、從 A 到 B 要走幾格。
層級遍歷：樹的 level-order（從上到下、由近到遠）。
二分圖判定（2-Coloring）：BFS 一層紅、一層藍，若碰到同色相鄰則不是二分圖。
最短邊數路徑：只要每條邊權重一樣（或視為 1），BFS 就是 Dijkstra 的簡化版。
Kahn 拓撲排序：雖然常說「入度 0 進 queue」，但本質也很像 BFS 的「一圈圈拿掉」。

標準 BFS 程式碼（含 dist）

C++ 版本（競賽常見）

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
vector<int> adj[N+1];
int dista[N+1];
bool vis[N+1];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m; 
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a); // 無向圖
    }
    // 初始化
    for(int i=1;i<=n;i++){
        dista[i] = -1;
    }

    queue<int> q;
    int start = 1;          // 起點，可依題目輸入
    q.push(start);
    vis[start] = true;
    dista[start] = 0;

    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : adj[u]){
            if(!vis[v]){
                vis[v] = true;
                dista[v] = dista[u] + 1;
                q.push(v);
            }
        }
    }

    // 輸出距離
    for(int i=1;i<=n;i++){
        cout << dista[i] << "\n";
    }
    return 0;
}

Python 版本（對應同概念）

from collections import deque
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)  # 無向圖

dist = [-1] * (n+1)
q = deque()
start = 1
q.append(start)
dist[start] = 0

while q:
    u = q.popleft()
    for v in adj[u]:
        if dist[v] == -1:          # 未訪
            dist[v] = dist[u] + 1
            q.append(v)

for i in range(1, n+1):
    print(dist[i])

注意：這裡是「入佇列時就把 dist[v] 設好」，這是 BFS 的標準寫法。

BFS 與 DFS 的差異與選擇時機

項目	BFS	DFS
搜尋順序	一圈圈往外（層級）	一路往下走到底再回頭
最短路徑	可以（無權圖）	不保證
實作結構	queue（先進先出）	遞迴或 stack（先進後出）
常見用途	最少步數、二分圖、層序	拓樸離點、回溯、樹遍歷
何時選它？	你要「最短幾步到達？」	你要「全部走一遍 / 找所有方案」