BFS 和 DFS：走迷宮的兩種策略

兩種找東西的方式

想像你在一間漆黑的迷宮裡找出口。兩種策略：

BFS（廣度優先）

像水從中心擴散——先看周圍 1 步能到的，再看 2 步，再看 3 步。

→ 用佇列 (Queue)：先進先出

DFS（深度優先）

像鑽地洞——選一條路鑽到底，撞牆才退回來換另一條。

→ 用堆疊 (Stack)：後進先出（或遞迴）

從同一張圖出發看差別

從 A 出發：

BFS 走訪順序：A → B → C → D → E → F → G（一層一層）
DFS 走訪順序：A → B → D → E → C → F → G（鑽到底再回來）

BFS 詳細跑一遍

用一個 Queue（先進先出）。已拜訪過的標記 visited，不要重複跑。

初始：    Queue: [A]    visited: {A}    走訪: []

取出 A，把 A 的鄰居 B, C 放入 queue
         Queue: [B, C] visited: {A,B,C} 走訪: [A]

取出 B，把 B 的鄰居 D, E 放入（A 已 visited 跳過）
         Queue: [C, D, E] visited: {A,B,C,D,E} 走訪: [A,B]

取出 C，把 C 的鄰居 F, G 放入
         Queue: [D, E, F, G] visited: 全部 走訪: [A,B,C]

取出 D, E, F, G（它們的鄰居都 visited 過）
         Queue: []     走訪: [A,B,C,D,E,F,G] ✓

Pseudocode：

Algorithm BFS(graph, start):

visited ← {start}

queue ← [start]

while queue not empty:

node ← queue.dequeue() // 從前面取出

process(node)

for neighbor in graph[node]:

if neighbor not in visited:

visited.add(neighbor)

queue.enqueue(neighbor) // 加到後面

DFS 詳細跑一遍

用 Stack（後進先出）或遞迴。

初始：    Stack: [A]    visited: {A}    走訪: []

取出 A（從頂端），把 B, C 推入
         Stack: [B, C] (C 在頂)    visited: {A,B,C}   走訪: [A]

取出 C（後進先出），推 F, G
         Stack: [B, F, G]   visited: +F,G   走訪: [A,C]

取出 G，鄰居都 visited
         Stack: [B, F]   走訪: [A,C,G]

取出 F，鄰居都 visited
         Stack: [B]   走訪: [A,C,G,F]

取出 B，推 D, E
         Stack: [D, E]   visited: +D,E   走訪: [A,C,G,F,B]

取出 E、D
         Stack: []   走訪: [A,C,G,F,B,E,D] ✓

Pseudocode（遞迴版最漂亮）：

visited ← {}

Algorithm DFS(graph, node):

if node in visited: return

visited.add(node)

process(node)

for neighbor in graph[node]:

DFS(graph, neighbor)

各自擅長什麼

用途	用哪個？	原因
找最短路徑（沒權重）	BFS	一層層擴散，第一次到達就是最短
偵測有無環	DFS	走到底容易發現「走回起點」
拓撲排序（DAG 排序）	DFS	經典應用
連通分量	都行	從某點開始走到的所有點
走樹的層次	BFS	一層一層列出來
走樹的根到葉	DFS	鑽到底

複雜度

兩個都一樣：

	時間	空間
BFS / DFS	O(V + E)	O(V)

（V = 頂點數，E = 邊數）

📝考試會這樣考

題型一：給圖和起點，寫出 BFS / DFS 走訪順序。 訣竅：題目通常說「鄰居按字母順序處理」，要照規定。不照順序會被扣分。

題型二：BFS 用什麼資料結構？DFS 用什麼？

BFS → Queue (FIFO)
DFS → Stack (LIFO) 或遞迴（其實遞迴也是用 call stack）

題型三：用 BFS 找最短路徑。 給無權重圖和起終點，問最少幾步到達。BFS 第一次抵達 = 最短路徑。

題型四：問為什麼 BFS 能找最短路徑，DFS 不行？ 答：BFS 是「逐層擴散」，第 k 次擴散覆蓋距離 ≤ k 的所有點，所以第一次到 t 的距離就是最短。 DFS 可能繞遠路才到 t。

這章記住

BFS = Queue + 一層層擴散，能找無權重最短路徑。
DFS = Stack 或遞迴 + 鑽到底，能偵測環、做拓撲排序。
兩者複雜度都是 O(V + E)。
都需要 visited 集合，不然會無限迴圈。