前兩篇，我們分別看過了兩種很常見的 Graph 搜尋方式：

Graph + Stack → DFS
Graph + Queue → BFS

DFS 選擇先沿著一條路一路往深處走。
BFS 則是一層一層往外擴張。
你可能會想一個問題：

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

如果只是看名字，可能會讓人以為這是一場演算法之間的競賽。
誰比較快？
誰比較省資源？
面試時到底應該優先寫哪一個？

但這種缺乏應用場景的探討偏向空談。
真正有意義的探討還是要回歸到實際需求：

你到底想找到什麼？

同一張 Graph，可以有完全不同的搜尋目標

來看看這次的捷運 Graph：

假設我們現在都從 A 開始搜尋。
DFS 可能按照這樣的順序：

A
↓
B
↓
D
↓
F

BFS 則可能：

A

B, C

D, E

F

兩個演算法最後都可能找到 F。
所以如果問題只是：

從 A 出發，有沒有辦法到 F？

那麼 DFS 和 BFS 都能解決。
這時就很難直接說 BFS 比 DFS 好 或是 DFS 比 BFS 好。
因為它們真正的差別，不只是「走路方式不同」。
而是：

不同搜尋策略，適合回答不同類型的問題

情況一：我只想找到「任意一個解」

一樣回到迷宮情境：

入口
 │
 ├── 路線 A ── 很深 ── 出口
 │
 └── 路線 B ── 出口

現在問題是：

我只想知道有沒有路能走出去？

我們並沒有要求：一定要最短。
也沒有要求：一定要經過最少節點。
只要找到一條可行路徑就可以，這種問題裡，DFS 很直覺。
因為 DFS 的策略就是：

先選一條路，往下探索到底

如果那條路剛好就是答案，可能很快就能找到。
概念上就是：

選一條路
↓
繼續深入
↓
如果找到答案
↓
停止

這類搜尋很常出現在：

• 迷宮是否存在出口
• 某個狀態是否可達
• 是否存在某種組合
• 是否存在符合條件的節點

這時候我們在意的就不是：

最好的解是哪一個？

只是要找到：

有沒有任何一個解？

情況二：我要找「最少步數」

但如果問題改成：

從 A 到 F，最少需要經過幾條 Edge？

問題前提就不同了，假設 Graph 是：

從 A 出發，存在兩條路：

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

DFS 如果先走 A → B → C → D → F，它確實找到答案了，但這不是最短路徑。
反觀 BFS 則會按照距離逐層探索：

level 0
A

level 1
B, E

level 2
C, F

當 BFS 第一次找到 F 時，我們就知道 A → E → F 使用了最少的 Edge。
這就是上一章提到的重要性質：

在未加權重的 graph 中，BFS 可以找到最少 Edge 數的最短路徑

注意這裡有一個很重要的前提未加權重，也就是每條 Edge 的成本可以視為一樣。

如果問題變成每一段捷運時間不同，或是每條道路成本不同，那麼 BFS 就不一定能直接代表真正的最低成本路徑。

目前只要先記得：

當「離起點有幾步」本身就是答案時，BFS 特別合理

情況三：答案可能藏得非常深

再來看另一種結構：

A
│
B
│
C
│
D
│
E
│
F
│
G

如果 Graph 很像一條非常深的路，而我們懷疑答案就在深處：

A → B → C → D → E → F → G

DFS 的策略就很直接。
它不需要先把附近所有可能性都探索完：

A
↓
B
↓
C
↓
D
↓
...

它是一直往深處走。

BFS 則會先處理所有同一層的節點，如果每一層都有大量分支：

        A
     / / \ \
    ...
   / / | \ \
  ...

那麼 BFS 在抵達很深的節點以前，可能需要先保留大量尚未探索的節點。
所以如果：

搜尋空間很寬，而答案可能很深

DFS 有時候會更符合問題形狀。
但這裡仍然不能直接簡化成：

深度大 → DFS 一定比較好

因為如果 Graph 中存在很深但沒有答案的分支，DFS 也可能花很多時間一路走錯。
還是那句話：

搜尋策略好不好，取決於問題本身

情況四：記憶體有限

DFS 和 BFS 還有一個非常實際的差別：

它們需要暫時保存哪些還沒探索的節點？

BFS 使用 Queue。
例如：

        A
     /  |  \
    B   C   D
   /|\ /|\ /|\
  ...

處理完 A 之後，Queue 裡可能先放：

B
C
D

接著再把下一層放進去：

E
F
G
H
I
J
...

如果 Graph 很寬，Queue 可能變得非常大。
因為 BFS 必須記住：

整個搜尋邊界上，所有之後要處理的節點

DFS 使用 Stack，或者 recursion。
它通常比較像：

A
↓
B
↓
E
↓
...

主要保留目前這條搜尋路徑，以及之後需要回頭處理的分支。
因此在某些很寬的搜尋空間中，DFS 的記憶體需求可能明顯小很多。
可以先用很粗略的直覺理解：

• BFS → 容易同時記住很多「同一層附近」的節點
• DFS → 容易主要記住目前「一路深入」的路徑

這也是為什麼：

如果記憶體本身就是限制條件，搜尋策略就不能只看答案正不正確

資源也是問題的一部分。

情況五：我要探索完整結構

有時候我們其實根本不是在找某個特殊答案。
例如：

把所有檔案掃描一次

或者：

把 Graph 中所有可以到達的 Node 都處理一次

這時 DFS 和 BFS 都可以完成 traversal。

DFS：

A
↓
B
↓
D
↓
回頭
↓
E
↓
回頭
↓
C

BFS：

A
↓
B, C
↓
D, E

如果最後所有 reachable nodes 都會被拜訪，那麼 DFS 或 BFS 都可以。
這時真正的選擇可能變成：

你希望以什麼順序看到資料？

例如檔案系統搜尋，有些場合我們希望：

先完整處理一個資料夾，再處理下一個

DFS 就很符合。

但如果我們希望：

先看距離 root 最近的內容，再逐層深入

BFS 可能比較符合需求。

所以即使目標都是遍歷完整 Graph，搜尋順序仍然可能影響後續處理方式。

DFS 和 BFS 不是速度排行榜

我們可以先整理成這樣：

這張表在提醒我們：

演算法沒有脫離問題條件的優劣

「比較快」其實少了一個重要問題

有人可能會問：

那 DFS 和 BFS 的時間複雜度誰比較好？

如果兩者都要完整遍歷一個以 adjacency list 表示的 Graph，通常都會看到類似：

O(V + E)

其中：

V = Node 數量
E = Edge 數量

因為最終都可能需要：

• 看過每個 Node
• 看過每條 Edge

所以單看 Big-O，兩者甚至可能是一樣的。
但這不代表它們實際行為完全相同。
因為搜尋順序不同會影響：

• 什麼時候找到答案
• 中途保存多少資料
• 能不能保證找到最少步數
• 哪些區域會先被探索

所以只問：

哪個比較快？

其實資訊不夠。
更完整的問題應該是：

在什麼 Graph 上、要找什麼答案、有哪些資源限制？

演算法其實是在利用問題條件

回頭看 BFS 為什麼可以找到 unweighted shortest path。
是因為 BFS 利用了這個問題條件：

每走過一條 Edge，都可以視為增加相同的成本

所以一層一層探索：

距離 0
距離 1
距離 2
距離 3

就有意義。
DFS 則利用另一種策略：

先深入，遇到死路再回頭

這在需要探索可能性、尋找任意解、處理階層結構時，就非常合理。

換句話說：

好的演算法，往往不是「做更多事情」，而是利用問題已經給你的條件

從 Data Structure 到 Algorithm

現在再回頭看前幾篇：

• Queue → 先進先出
• Stack → 後進先出

當它們被放進 Graph 裡之後，就不再只是保存資料的容器。
它們直接改變了：

下一個要探索誰？

於是：

• Graph + Stack → DFS
• Graph + Queue → BFS

這其實也是我們一路想建立的核心觀念：

資料結構本身會影響演算法的行為

Stack 和 Queue 保存的都可能是 Node。
真正不同的是下一個 Node 怎麼選？
而這個選擇，最後就變成完全不同的搜尋策略。

今天真正要記住的不是 DFS 還是 BFS

如果今天只記住：

• DFS 用 Stack
• BFS 用 Queue

其實還不夠完整，更重要的是建立這個思考順序：

我要找什麼？
↓
問題有哪些條件？
↓
我要以什麼順序探索？
↓
哪個 Data Structure 能表達這個順序？
↓
選擇 Algorithm

不單純是：

我會 BFS
↓
看看哪裡可以套 BFS

演算法真正重要的能力，不是記住更多名詞。
是看到問題時，會開始問：

這個問題真正要求我保證的是什麼？

小結

DFS 和 BFS 都是在 Graph 上搜尋。
差別主要來自：

DFS
→ 先深入
→ Stack / recursion

BFS
→ 先擴張
→ Queue

• 如果你只需要找到任意解，DFS 可能很直覺
• 如果你需要 unweighted graph 中的最少步數，BFS 更合適
• 如果 Graph 很寬、記憶體有限，DFS 的搜尋方式可能比較有利
• 如果希望按照距離逐層探索，BFS 就更符合問題語意
• 如果只是完整 traversal，兩者都可能完成工作，只是順序不同

所以今天最重要的結論是：

沒有脫離問題條件的「最好演算法」

真正重要的永遠是：

你到底想找到什麼？

到目前為止，我們比較 DFS 和 BFS 時，都把每一條 Edge 視為相同成本。
因此 BFS 找到的最少步數，也可以被理解成 unweighted Graph 裡的最短路徑。
但現實中的「最少步數」，不一定代表真正最好。

例如一條捷運路線只經過三站，可能需要 20 分鐘；另一條路線雖然經過五站，卻可能只要 10 分鐘。
這時真正影響選擇的就不只是經過幾條 Edge？

是去思考每一條 Edge 各自帶有多少：

• 時間
• 距離
• 費用

所以下一篇要問的是：

如果每一條 Edge 的成本不同，我們要怎麼找到真正成本最低的路？