BFS 與 DFS#

核心差異#

flowchart TB
    subgraph BFS["BFS 廣度優先：層層推進"]
        direction LR
        B1((1)) --> B2((2))
        B1 --> B3((3))
        B1 --> B4((4))
        B2 --> B5((5))
        B2 --> B6((6))
    end

    subgraph DFS["DFS 深度優先：一路到底"]
        direction TB
        D1((1)) --> D2((2))
        D2 --> D5((5))
        D5 --> D6((6))
        D2 -.-> D3((3))
        D1 -.-> D4((4))
    end

特性	BFS（廣度優先）	DFS（深度優先）
策略	層層推進（地毯式）	一路到底（鑽研式）
資料結構	佇列 (Queue)	堆疊 (Stack) / 遞迴
最短路徑	保證最短（無權圖）	不保證
實現方式	迭代	遞迴（推薦）或迭代

BFS 廣度優先搜尋#

核心概念#

從起點開始，先訪問所有距離為 1 的節點，再訪問距離為 2 的節點…

     1
   / | \
  2  3  4
 /\    / \
5  6  7   8

訪問順序：1 → 2,3,4 → 5,6,7,8

模板程式碼#

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = {start}

    while queue:
        node = queue.popleft()
        # 處理當前節點

        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

關鍵：將節點加入佇列時立即標記 visited，避免重複入隊。

階層走訪技巧#

while queue:
    level_size = len(queue)  # 鎖定當前層數量
    for _ in range(level_size):
        node = queue.popleft()
        # 處理當前層節點

DFS 深度優先搜尋#

核心概念#

選定一條路走到底，無路可走時回溯。

訪問順序：1 → 2 → 5 → 6 → 3 → 4（遞迴自然形成的順序）

遞迴模板（推薦）#

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)

    # 處理當前節點

    for neighbor in get_neighbors(node):
        dfs(neighbor, visited)

迭代模板#

def dfs_iterative(start):
    stack = [start]
    visited = set()

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)

        # 處理當前節點

        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                stack.append(neighbor)

建議：面試時優先使用遞迴寫法，程式碼更簡潔，遞迴堆疊自動維護狀態。

樹 vs 圖的處理差異#

結構	是否需要 visited
樹	通常不需要（無環）
圖	必須（可能有環）

圖的搜尋必須維護 visited 集合！否則會陷入無限迴圈。

應用場景#

場景	適用演算法
最短路徑（無權）	BFS
連通分量	BFS 或 DFS
拓撲排序	DFS（或 Kahn）
迷宮問題	BFS（最短）或 DFS
島嶼數量	DFS（常用）

社交網路的 N 度好友

問題：找出某用戶的三度好友（好友的好友的好友）

解法：BFS 是最佳選擇

第 1 層：一度好友
第 2 層：二度好友
第 3 層：三度好友

使用階層走訪技巧，控制搜尋深度即可。