演算法詳解：BFS 與 DFS（廣度優先搜尋與深度優先搜尋）

luk 收錄於 Algorithm

2024-12-20 約 1100 字預計閱讀 5 分鐘

前言

BFS（Breadth-First Search，廣度優先搜尋）和 DFS（Depth-First Search，深度優先搜尋）是圖論和樹結構中最基礎也最重要的兩個演算法。幾乎所有的圖和樹相關問題都會用到這兩種遍歷方式。

本文將從基礎概念開始，逐步深入到實際應用，幫助你徹底掌握這兩個演算法。

核心概念

什麼是 BFS？

廣度優先搜尋（BFS）是一種圖遍歷演算法，它從起始節點開始，先訪問所有相鄰的節點，然後再訪問這些節點的相鄰節點，以此類推。就像水波紋一樣，一圈一圈地向外擴散。

什麼是 DFS？

深度優先搜尋（DFS）是另一種圖遍歷演算法，它從起始節點開始，沿著一條路徑盡可能深地探索，直到無法繼續，然後回溯到上一個節點，探索其他路徑。就像走迷宮一樣，先走到底，走不通再回頭。

視覺化比較

樹結構：
       A
      / \
     B   C
    / \   \
   D   E   F
  /
 G

BFS 遍歷順序：A → B → C → D → E → F → G（逐層）
DFS 遍歷順序：A → B → D → G → E → C → F（深入）

BFS 詳解

BFS 的核心思想

使用**佇列（Queue）**資料結構
先進先出（FIFO）原則
逐層擴展，確保最短路徑

BFS 基本模板

from collections import deque

def bfs(start):
    # 初始化佇列和訪問集合
    queue = deque([start])
    visited = set([start])
    
    while queue:
        # 取出佇列最前面的節點
        node = queue.popleft()
        
        # 處理當前節點
        process(node)
        
        # 將鄰居節點加入佇列
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS 在二元樹中的應用

1. 層序遍歷

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        level_size = len(queue)
        
        # 處理當前層的所有節點
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

2. 找最短路徑（無權重圖）

def shortestPath(graph, start, end):
    queue = deque([(start, [start])])
    visited = set([start])
    
    while queue:
        node, path = queue.popleft()
        
        if node == end:
            return path
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # 無法到達

BFS 的特點

特性	說明
資料結構	佇列（Queue）
空間複雜度	O(w)，w 是最大寬度
時間複雜度	O(V + E)
適用場景	最短路徑、層級遍歷
記憶體使用	較高（需要存儲整層）

DFS 詳解

DFS 的核心思想

使用堆疊（Stack）或遞迴
後進先出（LIFO）原則
深入探索，直到無路可走

DFS 基本模板

遞迴版本

def dfs_recursive(node, visited=None):
    if visited is None:
        visited = set()
    
    # 標記為已訪問
    visited.add(node)
    
    # 處理當前節點
    process(node)
    
    # 遞迴訪問鄰居
    for neighbor in get_neighbors(node):
        if neighbor not in visited:
            dfs_recursive(neighbor, visited)

迭代版本（使用堆疊）

def dfs_iterative(start):
    stack = [start]
    visited = set()
    
    while stack:
        node = stack.pop()
        
        if node in visited:
            continue
            
        visited.add(node)
        process(node)
        
        # 將鄰居壓入堆疊
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                stack.append(neighbor)

DFS 在二元樹中的應用

1. 前序遍歷（Pre-order）

def preorderTraversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        
        result.append(node.val)  # 先處理根
        dfs(node.left)           # 再處理左
        dfs(node.right)          # 最後處理右
    
    dfs(root)
    return result

2. 中序遍歷（In-order）

def inorderTraversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        
        dfs(node.left)           # 先處理左
        result.append(node.val)  # 再處理根
        dfs(node.right)          # 最後處理右
    
    dfs(root)
    return result

3. 後序遍歷（Post-order）

def postorderTraversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        
        dfs(node.left)           # 先處理左
        dfs(node.right)          # 再處理右
        result.append(node.val)  # 最後處理根
    
    dfs(root)
    return result

DFS 的特點

特性	說明
資料結構	堆疊（Stack）或遞迴
空間複雜度	O(h)，h 是最大深度
時間複雜度	O(V + E)
適用場景	路徑搜尋、回溯、拓撲排序
記憶體使用	較低（只需存儲路徑）

BFS vs DFS 完整比較

執行過程視覺化

圖結構：
    1 ─── 2
    │     │
    │     │
    3 ─── 4
    │
    │
    5

BFS 執行過程：
步驟 1: queue=[1], visited={1}
步驟 2: queue=[2,3], visited={1,2,3}
步驟 3: queue=[3,4], visited={1,2,3,4}
步驟 4: queue=[4,5], visited={1,2,3,4,5}
訪問順序：1 → 2 → 3 → 4 → 5

DFS 執行過程：
步驟 1: stack=[1], visited={1}
步驟 2: stack=[2,3], visited={1}
步驟 3: stack=[2,5], visited={1,3}
步驟 4: stack=[2], visited={1,3,5}
步驟 5: stack=[4], visited={1,2,3,5}
訪問順序：1 → 3 → 5 → 2 → 4

選擇指南

使用 BFS	使用 DFS
尋找最短路徑	尋找所有可能路徑
層級相關問題	需要回溯的問題
最近的目標	迷宮、拼圖問題
社交網路分析	檢測環
廣播、擴散	拓撲排序

經典應用題目

BFS 經典題

1. 二元樹的最小深度

def minDepth(root):
    if not root:
        return 0
    
    queue = deque([(root, 1)])
    
    while queue:
        node, depth = queue.popleft()
        
        # 找到第一個葉子節點
        if not node.left and not node.right:
            return depth
        
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

2. 01 矩陣（最短距離）

def updateMatrix(mat):
    m, n = len(mat), len(mat[0])
    queue = deque()
    
    # 將所有 0 加入佇列
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                queue.append((i, j))
            else:
                mat[i][j] = float('inf')
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        x, y = queue.popleft()
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < m and 0 <= ny < n:
                if mat[nx][ny] > mat[x][y] + 1:
                    mat[nx][ny] = mat[x][y] + 1
                    queue.append((nx, ny))
    
    return mat

DFS 經典題

1. 路徑總和

def hasPathSum(root, targetSum):
    if not root:
        return False
    
    # 葉子節點
    if not root.left and not root.right:
        return root.val == targetSum
    
    # 遞迴檢查左右子樹
    return (hasPathSum(root.left, targetSum - root.val) or 
            hasPathSum(root.right, targetSum - root.val))

2. 島嶼數量

def numIslands(grid):
    if not grid:
        return 0
    
    m, n = len(grid), len(grid[0])
    count = 0
    
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
            return
        
        grid[i][j] = '0'  # 標記為已訪問
        
        # 遞迴訪問四個方向
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    
    return count

進階技巧

1. 雙向 BFS

用於加速搜尋，從起點和終點同時開始：

def bidirectionalBFS(graph, start, end):
    if start == end:
        return 0
    
    front = {start}
    back = {end}
    visited = {start, end}
    distance = 0
    
    while front and back:
        distance += 1
        
        # 選擇較小的集合擴展
        if len(front) > len(back):
            front, back = back, front
        
        next_front = set()
        for node in front:
            for neighbor in graph[node]:
                if neighbor in back:
                    return distance
                
                if neighbor not in visited:
                    visited.add(neighbor)
                    next_front.add(neighbor)
        
        front = next_front
    
    return -1

2. DFS 與記憶化

結合動態規劃的 DFS：

def longestIncreasingPath(matrix):
    if not matrix:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    memo = {}
    
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        max_length = 1
        
        for dx, dy in directions:
            x, y = i + dx, j + dy
            if (0 <= x < m and 0 <= y < n and 
                matrix[x][y] > matrix[i][j]):
                max_length = max(max_length, 1 + dfs(x, y))
        
        memo[(i, j)] = max_length
        return max_length
    
    return max(dfs(i, j) for i in range(m) for j in range(n))

時間與空間複雜度總結

時間複雜度

兩者在圖遍歷中的時間複雜度都是 O(V + E)：

V：頂點數
E：邊數

空間複雜度

BFS：O(w)，w 是圖的最大寬度
DFS：O(h)，h 是圖的最大深度

在最壞情況下（完全圖），兩者都是 O(V)。

常見錯誤和注意事項

1. BFS 忘記標記訪問

# ❌ 錯誤：可能重複訪問
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        queue.append(neighbor)

# ✅ 正確：使用 visited 集合
visited = set([start])
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

2. DFS 遞迴深度限制

# Python 預設遞迴深度約 1000
import sys
sys.setrecursionlimit(10000)  # 增加限制

# 或使用迭代版本避免此問題

3. 圖中的環處理

# DFS 需要三種狀態來檢測環
WHITE = 0  # 未訪問
GRAY = 1   # 訪問中
BLACK = 2  # 已完成

def hasCycle(graph):
    color = defaultdict(int)
    
    def dfs(node):
        if color[node] == GRAY:
            return True  # 發現環
        
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] != BLACK:
                if dfs(neighbor):
                    return True
        
        color[node] = BLACK
        return False
    
    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    
    return False

面試技巧

先問清楚：是樹還是圖？有環嗎？有權重嗎？
選擇合適的方法：最短路徑用 BFS，需要所有路徑用 DFS
注意邊界條件：空圖、單節點、自環等
優化空間：能否原地修改？能否減少 visited 的使用？
說明複雜度：清楚解釋時間和空間複雜度

總結

BFS 和 DFS 是演算法世界的兩大基石：

BFS 像是「齊頭並進」，適合找最短路徑和層級問題
DFS 像是「一條道走到黑」，適合遍歷所有可能和回溯問題

掌握這兩個演算法的關鍵是：

理解原理：為什麼一個用佇列，一個用堆疊
熟悉模板：能快速寫出基本框架
識別場景：知道什麼時候用哪個
大量練習：通過刷題加深理解

記住：沒有絕對的好壞，只有更適合的選擇！