圖與 BFS

一層一層走出去，先碰到的就是最近的。 · ⏱ 約 40 分鐘

你會學到三件事

1. 圖怎麼存：鄰接表
2. BFS 用 queue，而它找到的是最短步數
3. dist 陣列同時當「走過沒」和「幾步」

開始之前

前面的資料都是一排或一張表，而圖不是：它是「誰連到誰」。

地圖、社交關係、迷宮、課程先修——這些都是圖。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、鄰接表

一張圖最常見的存法：

1vector<vector<int>> g;      // g[u] ＝ u 連到哪些點

g[0] = {1, 2} 的意思是「0 連到 1 和 2」。

⚠️ 無向圖要兩邊都加：

1g[a].push_back(b);2g[b].push_back(a);      // ← 漏了就變成單向

二、BFS：一層一層

照著打上這一段：

1vector<int> dist(4, -1);2queue<int> q;3q.push(0);4dist[0] = 0;5while (!q.empty()) {6    int u = q.front();7    q.pop();8    vector<int> nb = g[u];9    for (int v : nb) {10        if (dist[v] == -1) {11            dist[v] = dist[u] + 1;12            q.push(v);13        }14    }15}

!q.empty() 那一格在積木上是「… 是否為空」——前面再加一個「不是」。

流程：

起點進佇列 → 拿一個出來 → 把它沒走過的鄰居都放進去 → 重複

因為 queue 是先進先出，距離 1 的會在距離 2 的前面全部處理完， 所以它是一層一層擴散的。

三、🔴 dist 一個陣列做兩件事

dist 同時回答「走到沒」和「走幾步」：

1if (dist[v] == -1) {2    dist[v] = dist[u] + 1;3    q.push(v);4}

-1 代表「還沒走過」，其他值代表「幾步到得了」。

⚠️ 標記要在 push 的時候做，不是 pop 的時候。

在 pop 時才標記的話，同一個點可能被 push 好幾次。 佇列會爆掉，而答案還是對的，所以很難發現。

四、🔴 BFS 找到的就是最短

第一次碰到某個點時，那個距離就是最短的。

因為 BFS 是一層一層走：距離 1 的全部處理完，才會處理距離 2 的。 所以你不可能「先用 3 步走到、之後才發現 2 步可以到」。

⚠️ 前提是每條邊的長度一樣。邊有不同權重的話 BFS 會給出錯的答案， 那時要用 Dijkstra：把 queue 換成第 7 課的 priority_queue， 每次先拿「目前已知距離最短的那個點」。

兩者的程式碼幾乎一樣，差別只在那個容器，而結果完全不同。

完成的樣子

1#include <iostream>2#include <queue>3#include <vector>4using namespace std;5int main() {6    vector<int> a0;7    a0.push_back(1);8    a0.push_back(2);9    vector<int> a1;10    a1.push_back(3);11    vector<int> a2;12    vector<int> a3;13    vector<vector<int>> g;14    g.push_back(a0);15    g.push_back(a1);16    g.push_back(a2);17    g.push_back(a3);18    vector<int> dist(4, -1);19    queue<int> q;20    q.push(0);21    dist[0] = 0;22    while (!q.empty()) {23        int u = q.front();24        q.pop();25        vector<int> nb = g[u];26        for (int v : nb) {27            if (dist[v] == -1) {28                dist[v] = dist[u] + 1;29                q.push(v);30            }31        }32    }33    cout << dist[3] << endl;34    return 0;35}

（0 → 1 → 3，所以 dist[3] 是 2。）

換你了

把 queue 換成 stack（q.front() 改成 q.top()）， 執行看看 dist[3] 變成什麼。

同一段程式，換一個容器，就從 BFS 變成 DFS， 而 DFS 找到的不保證是最短的。

到編輯器做這一題：練習：把 queue 換成 stack，看 dist[3] 變什麼

做一個

五個點，邊是 0→1、0→2、1→3、2→3、3→4。 從 0 出發，印出每個點的最短步數（編號 步數）。

🔴 點 3 有兩條路走得到（經過 1 或經過 2），而它們一樣長。 BFS 的 if (dist[v] == -1) 那一行就是在說「第一次到的那次最短」。

到編輯器做這一題：做一個：每個點離起點幾步

這一課你做了什麼

• 你用鄰接表存了一張圖
• 你用 queue 一層一層走出去
• 你用一個 dist 陣列同時記了「走過沒」和「幾步」

如果卡住了