上一篇談到 DFS 時，我們做了一個很明確的選擇：

先沿著一條路一路走到底

這是一種搜尋策略。
但如果今天問題換方向了呢？

假設我們面前不是迷宮，而是一張捷運路網：

現在我們不再問：

能不能從 A 走到 F？

而是問：

從 A 到 F，最少要經過幾個站？

這時候，一路走到底可能就不是最適合的做法了。
因為我們真正關心的是：

離 A 最近的站有哪些？再下一層有哪些？

這正是 Breadth-First Search，簡稱 BFS，很擅長處理的問題。

先不要急著走太遠

假設我們現在站在 A，若從 A 出發，可以直接到 B 和 C。
簡單來說就是距離 A 一步。

接著，我們再從 B、C 往外看，B 可以到 D 和 E；
C 也可以到 E；
扣掉已經看過的站之後，下一層就是 D 和 E。
也就是距離 A 兩步。

再繼續往外是 F，所以我們會得到：

Level 0
A

Level 1
B C

Level 2
D E

Level 3
F

這種搜尋方式的想法是：

先把距離目前位置最近的節點全部處理完，再往更遠的一層前進

這就是 breadth-first 的意思。

Breadth-first：先往「寬」的方向找

如果 DFS 的直覺是：

先深入
↓
走到底
↓
再回頭

那 BFS 的直覺就是：

先看附近
↓
再看更遠一層
↓
再看下一層

可以把兩種策略想成：

DFS

A
└─ B
   └─ D
      └─ F

可能先一路鑽進某一條路。
而 BFS 比較像：

A

↓ 第一圈

B   C

↓ 第二圈

D   E

↓ 第三圈

F

它會一圈一圈向外擴張。
這裡的「圈」就是 BFS 很重要的一個概念：

level

Level 其實就是「距離」

在這張捷運 Graph 裡：

如果每搭一站的成本都一樣，我們可以把經過一條 Edge，理解成距離 +1。
所以從 A 開始：

A       → level 0

B、C    → level 1

D、E    → level 2

F       → level 3

BFS 最重要的特性之一，就是：

它會按照距離由近到遠探索節點

因此第一次走到 F 時，我們就知道：

A → ? → ? → F

這條路使用的 Edge 數量已經是最少的。
以這個例子來說，可以走：

• A → B → D → F
• A → B → E → F
• A → C → E → F

都是 3 次移動。
因此：

A 到 F 的最短距離 = 3 edges

如果把起點與終點也算進去，路徑上會有 4 個站。
這也是為什麼實際討論「最少幾站」時，最好先說清楚我們算的是：

Edge 數量 還是 經過的 Node 數量

在 Graph 演算法裡，通常會把這種距離理解成經過多少條 Edge。

為什麼 BFS 可以找到最短路徑？

不是 BFS 有什麼黑魔法，關鍵起作用的，還是在它的搜尋順序。
假設我們從 A 開始：

level 0 → A

BFS 一定會先把所有距離 1 的節點找出來：

level 1 → B、C

才會開始處理距離 2：

level 2 → D、E

然後才會碰到距離 3：

level 3 → F

所以如果 F 第一次出現在 level 3，它就不可能還存在一條距離 2 的路徑。
因為如果有，BFS 在處理 level 2 時就已經遇到它了。

也就是說：

BFS 不需要把所有可能路徑都走完，再回頭比較哪條最短

它的搜尋順序本身，就保證了先找到的較近，後找到的較遠。
因此在適合的條件下，第一次找到目標時，就已經得到最短距離。

這就是 unweighted shortest path

不過這裡有一個非常重要的前提。
我們剛剛把每一段捷運連線都當成 成本 = 1，也就是 A → B 和 D → F 等價，沒有誰比較貴、誰比較遠。
我們只在乎經過幾條 Edge，這類 Graph 通常可以稱為 unweighted graph。
或者更精準地說：

在我們目前的問題裡，每條 Edge 的成本都被視為相同

所以 BFS 很適合拿來解 unweighted shortest path。
大概的意思是：

沒有不同 Edge 權重時的最短路徑問題

但真實捷運的「最快」不一定等於「最少站」

這裡也可以看出一個很重要的模型差異。
如果問題只是：

最少經過幾站？

那我們可以把每條 Edge 都當成成本 1。
但如果問題改成：

哪一條路最快到？

前提不同問題就不一樣了，因為不同站之間可能需要不同時長，甚至還有不同類：

• 轉乘時間
• 等待時間
• 步行時間

這時候 A → B 和 B → D 就不能再視為完全相同的成本。
Graph 可能會變成：

那問題已經不是問：最少幾條 Edge？
而是改問：所有 Edge cost 加起來最小是多少？
這時單純 BFS 就不夠了。
後面我們還會再看到其他最短路徑演算法。
現在只需要先記住：

BFS 找到的是「每一步成本相同」時的最短路徑

那 BFS 為什麼需要 Queue？

看到這裡，可以重新想起 Day 2 的 Queue。
當時我們說 Queue 的規則是先進來先處理 FIFO，文章中 Queue 看起來只是一個適合排隊情境的資料結構。
但到了 BFS，它開始真正成為演算法的一部分。

假設從 A 開始，先把 A 放進 Queue：

Queue

[A]

取出 A，發現 B、C：

Queue

[B, C]

接著一定先處理 B：

Queue

[C, D, E]

然後再處理 C。

因為 B、C 都是 level 1，所以它們一定會排在 D、E，這些 level 2 的節點前面。

Queue 的 FIFO 規則，自然維持了：

level 0
↓
level 1
↓
level 2
↓
level 3

這種搜尋順序，也就是 Graph + Queue → BFS。
這次 Queue 不只是生活中的比喻，它直接決定了演算法的行為。

如果改成 Stack 呢？

這也是一個很有意思的比較。
假設我們不是用 Queue，而是用 Day 4 的 Stack。

Stack 的規則是 最後加入最先處理 LIFO。

那搜尋就很容易變成：

A
↓
B
↓
D
↓
F

沿著某條路一直深入，這正好是上一篇看到的 DFS。
所以我們現在可以得到一個很漂亮的對照：

Graph + Stack
→ DFS

Graph + Queue
→ BFS

Graph 本身沒有規定你應該怎麼搜尋。
真正改變搜尋策略的是順序：

下一個要處理哪個 Node？

這個問題，其實從前幾天就一直出現。

visited 還是不能少

和 DFS 一樣，BFS 在 Graph 裡也需要處理 cycle。
例如：

如果沒有記錄 visited：

A → B → E → C → A → B → ...

就可能重複走訪同一批節點。
所以 BFS 通常仍然會搭配 visited，記錄哪些 Node 已經看過。
概念上會像 Queue + Visited，每發現一個新的 Node：

1. 確認它還沒有 visited
2. 標記為 visited
3. 放進 Queue
4. 之後輪到它時，再探索它的鄰居

注意通常是在「放進 Queue 時」就標記 visited，而不是等取出來才標記。
否則同一個 Node 可能被不同鄰居重複加入 Queue。

用 JavaScript 看 BFS 的骨架

這篇的重點仍然不是背程式碼。
但我們可以看看 BFS 的結構到底長什麼樣子。
假設 Graph 使用 Day 8 看過的 Adjacency List：

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "E"],
  D: ["B", "F"],
  E: ["B", "C", "F"],
  F: ["D", "E"],
};

一個簡化的 BFS 可以寫成：

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);

  while (queue.length > 0) {
    const node = queue.shift();

    console.log(node);

    for (const neighbor of graph[node]) {
      if (visited.has(neighbor)) continue;

      visited.add(neighbor);
      queue.push(neighbor);
    }
  }
}

如果從 A 開始：

bfs(graph, "A");

可能得到：

A
B
C
D
E
F

這段 code 最值得看的，其實只有兩件事：

queue.push(neighbor);

新發現的 Node 排到後面。
以及：

const node = queue.shift();

每次從最前面拿出下一個 Node。
這個 FIFO 的順序就是 BFS breadth-first 行為的來源。

如果真的要算距離呢？

如果目標是：

從 A 到每個站最少要走幾步？

我們可以在 Queue 裡一起保存距離：

function bfsDistance(graph, start) {
  const queue = [[start, 0]];
  const visited = new Set([start]);

  while (queue.length > 0) {
    const [node, distance] = queue.shift();

    console.log(node, distance);

    for (const neighbor of graph[node]) {
      if (visited.has(neighbor)) continue;

      visited.add(neighbor);
      queue.push([neighbor, distance + 1]);
    }
  }
}

結果可能是：

A 0
B 1
C 1
D 2
E 2
F 3

這其實就是前面說的 level：

distance === level

至少在這個 unweighted Graph 裡，可以這樣理解。

但 JavaScript 的 shift() 呢？

如果還記得 Day 2，我們當時提過：

queue.shift();

雖然可以很直觀地模擬 Queue，但在一般 Array 實作下，移除第一個元素可能伴隨後續元素重新調整的成本。
所以正式實作 BFS 時，常見做法不是每次真的 shift()。
例如可以使用一個 index：

function bfs(graph, start) {
  const queue = [start];
  let head = 0;

  const visited = new Set([start]);

  while (head < queue.length) {
    const node = queue[head++];

    for (const neighbor of graph[node]) {
      if (visited.has(neighbor)) continue;

      visited.add(neighbor);
      queue.push(neighbor);
    }
  }
}

概念完全一樣：

前面進來的 → 前面處理

只是我們不需要真的一直刪掉 Array 第一個元素。
不過這仍然只是實作細節。
理解 BFS 時更重要的，是 Queue 所提供的順序規則。

回頭看 Day 2，Queue 的意義已經不一樣了

Day 2 我們從超商排隊開始。
那時候 Queue 解決的是：誰先來？
所以 先進先出 FIFO 很合理。

到了今天，Queue 被放進 Graph 裡。
它解決的問題變成：下一個應該探索誰？

因為先發現的 Node 通常代表距離起點比較近，Queue 讓這些比較近的節點先被處理。
最後形成 breadth-first，所以資料結構並不是學完一篇就結束了。
它們會成為後面演算法的地基。

Queue
↓
ordering rule
↓
BFS
↓
unweighted shortest path

DFS 和 BFS 其實都在回答同一個問題

把上一篇和今天放在一起看：

DFS
→ 先沿一條路深入到底

BFS
→ 先探索附近，再逐層向外

它們面對的可能是同一張 Graph，資料相同但差異在：

我們決定用什麼順序探索資料。

這也再次回到整個系列一直在談的核心：

Data Structure 和 Algorithm 並不是互相獨立的兩門知識。

當我們選擇 Stack：

Graph + Stack → DFS

當我們選擇 Queue：

Graph + Queue → BFS

資料結構所提供的操作規則，會直接塑造演算法的行為。

今天真正要記住的不是 BFS code

如果只記住：

while (queue.length) {
  // ...
}

其實很容易忘，更重要的是理解它背後的理由：

當我們希望按照「離起點由近到遠」的順序搜尋時，就需要一種能維持這個順序的策略

Queue 的 FIFO 正好提供了這個順序。
於是：

Graph + Queue
↓
Breadth-First Search
↓
一層一層向外探索
↓
Unweighted Shortest Path

所以 BFS 讓我們理解的是：

搜尋順序本身，就是演算法的一部分

BFS 和上一篇的 DFS，都能在 Graph 裡尋找答案。
但它們選擇下一個 Node 的方式不同：

• DFS → 先沿著一條路深入
• BFS → 先探索距離起點較近的 Node

如果只是想知道某個 Node 能不能到達，兩者可能都能做到。
但如果要找最少步數、探索很深的結構，或受到記憶體限制，它們的表現與適用情境就可能完全不同。

所以下一個問題是：

DFS 和 BFS，到底哪一個比較好？

而這個問題真正要比較的是：

我們到底想找到什麼？