BFS 和 DFS 編程思想、框架、技巧及經典例題總結

一、核心編程思想

BFS（廣度優先搜索）

核心思想：以「層次遍歷」為核心，從起點出發，優先探索距離起點最近的節點，逐層擴散遍歷。
本質：通過「隊列」實現 “先入先出” 的順序，保證每次處理的都是當前層的所有節點，適合解決「最短路徑」「層次遍歷」「連通性判斷（無權圖）」等問題。
特點：
- 遍歷過程中節點的 “距離”（步數）是遞增的，首次到達目標節點時的路徑即為最短路徑（無權圖 / 等權圖）。
- 空間復雜度較高（需存儲當前層所有節點），但時間復雜度穩定。

DFS（深度優先搜索）

核心思想：以「深度優先」為核心，從起點出發，沿著一條路徑深入到底，直到無法前進時回溯，換另一條路徑繼續探索。
本質：通過「遞歸棧」或「手動棧」實現 “后入先出” 的順序，適合解決「連通性判斷」「排列組合」「路徑搜索」「回溯剪枝」等問題。
特點：
- 遍歷過程具有 “回溯” 特性，可通過剪枝優化無效路徑，減少計算量。
- 空間復雜度由遞歸深度（或棧深度）決定，可能因深度過大導致棧溢出（需注意遞歸邊界）。

二、通用編程框架

BFS 框架（模板）
基礎模板（樹 / 圖通用）

def bfs(start, target):# 初始化隊列（存儲待處理節點）from collections import dequequeue = deque([start])# 初始化visited（避免重復訪問，圖必備；樹可省略，但需處理父節點回退）visited = set([start])# 記錄距離/層數（可選，按需添加）distance = 0  while queue:# 處理當前層的所有節點（關鍵：先獲取當前層節點數）level_size = len(queue)for _ in range(level_size):# 彈出隊首節點current = queue.popleft()# 若找到目標，返回結果if current == target:return distance  # 或其他結果# 遍歷當前節點的所有相鄰節點for neighbor in get_neighbors(current):if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)# 層數/距離+1（每處理完一層遞增）distance += 1# 未找到目標return -1

關鍵組件:
- 隊列：存儲待處理的節點，保證 “先入先出”。
- visited 集合：標記已訪問節點（圖中必用，避免環導致的死循環；樹中可省略，但需通過父節點指針避免回退）。
- 層次處理：通過level_size控制每層節點的批量處理，實現 “層次遍歷”。

DFS 框架（模板）
遞歸版（簡潔，適合深度不太大的場景）

def dfs(current, visited, target):# 終止條件：找到目標或越界if current == target:return True  # 或記錄路徑if current is invalid: # 剪枝return False# 標記當前節點為已訪問visited.add(current)# 遍歷所有相鄰節點for neighbor in get_neighbors(current):if neighbor not in visited:# 遞歸探索下一層if dfs(neighbor, visited, target):return True  # 找到目標，提前返回# 回溯：若需恢復狀態（如排列組合問題），此處可移除標記# visited.remove(current)  # 視問題而定是否需要return False  # 未找到目標

迭代版（手動棧，適合深度較大的場景，避免遞歸棧溢出）

def dfs_iterative(start, target):stack = [start]  # 手動棧visited = set([start])while stack:current = stack.pop()  # 彈出棧頂節點（最后入棧的節點）# 找到目標，返回結果if current == target:return True# 遍歷相鄰節點（注意：棧是后入先出，若需按順序遍歷，可反向添加）for neighbor in reversed(get_neighbors(current)):if neighbor not in visited:visited.add(neighbor)stack.append(neighbor)return False

關鍵組件：
- 棧：遞歸時隱式使用函數調用棧，迭代時手動維護棧，保證 “后入先出”。
- visited 集合：同 BFS，避免重復訪問。
- 回溯：在排列組合等問題中，需在遞歸返回后移除visited標記，允許節點被其他路徑重新訪問。

三、實用技巧

BFS 技巧

雙向 BFS 優化：當起點和終點明確時（如最短路徑問題），可從起點和終點同時開始 BFS，相遇時終止，大幅減少搜索空間（適用于節點數量龐大的場景，如「打開轉盤鎖」）。
距離記錄：通過數組或哈希表記錄每個節點到起點的距離，無需額外變量（如distance[node] = distance[current] + 1）。
層次信息利用：在層次遍歷問題中（如二叉樹每層節點之和），通過level_size區分不同層，方便按層處理數據。

DFS 技巧

剪枝優化：在遞歸過程中提前判斷無效路徑（如 “和超過目標的組合”“已存在重復的排列”），直接返回，減少計算量。
記憶化搜索：對重復子問題（如動態規劃中的遞歸場景），用哈希表記錄已計算的結果，避免重復計算（如「斐波那契數列」「最長遞增子序列」的遞歸實現）。
路徑跟蹤：在需要記錄具體路徑的問題中（如「所有可能的路徑」），通過列表在遞歸時添加節點，回溯時移除節點，動態維護路徑。

四、經典例題解析

BFS 經典例題
例題 1：二叉樹的層序遍歷（LeetCode 102）

問題：給定二叉樹的根節點，返回按層序遍歷的節點值（逐層從左到右）。
思路：用 BFS 按層處理節點，每層遍歷前記錄隊列長度（當前層節點數），依次彈出并收集值，再將子節點入隊。
代碼：

def levelOrder(root):if not root:return []from collections import dequequeue = deque([root])result = []while queue:level_size = len(queue)current_level = []for _ in range(level_size):node = queue.popleft()current_level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(current_level)return result

例題 2：打開轉盤鎖（LeetCode 752）

問題：轉盤鎖有 4 個數字（0-9），每次可轉動一個數字 ±1（如 0→9 或 0→1）。給定死亡數字列表（不可經過），求從 “0000” 到目標數字的最少步數，無法到達則返回 - 1。
思路：BFS 求最短路徑，每次轉動生成 8 種可能的下一個狀態（4 個位置，每個 ±1），用 visited 和死亡列表過濾無效狀態，- 雙向 BFS 可優化效率。
核心代碼：

def openLock(deadends, target):from collections import dequedead = set(deadends)start = "0000"if start in dead:return -1if start == target:return 0# BFS初始化queue = deque([start])visited = set([start])steps = 0while queue:steps += 1level_size = len(queue)for _ in range(level_size):current = queue.popleft()# 生成所有可能的下一個狀態for i in range(4):for d in (-1, 1):# 轉動第i位數字（0-9循環）new_digit = (int(current[i]) + d) % 10next_str = current[:i] + str(new_digit) + current[i+1:]if next_str == target:return stepsif next_str not in visited and next_str not in dead:visited.add(next_str)queue.append(next_str)return -1

DFS 經典例題
例題 1：島嶼數量（LeetCode 200）

問題：給定二維網格，‘1’ 表示陸地，‘0’ 表示水，求島嶼數量（相鄰陸地相連，上下左右為相鄰）。
思路：遍歷網格，遇到未訪問的 ‘1’ 時啟動 DFS，將所有相連的 ‘1’ 標記為已訪問（避免重復計數），每啟動一次 DFS 即增加一個島嶼。也可以使用BFS。
代碼：

def numIslands(grid):if not grid:return 0rows, cols = len(grid), len(grid[0])visited = [[False for _ in range(cols)] for _ in range(rows)]count = 0def dfs(i, j):# 越界或非陸地或已訪問，直接返回if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == '0' or visited[i][j]:returnvisited[i][j] = True  # 標記為已訪問# 遞歸探索上下左右dfs(i+1, j)dfs(i-1, j)dfs(i, j+1)dfs(i, j-1)for i in range(rows):for j in range(cols):if grid[i][j] == '1' and not visited[i][j]:count += 1dfs(i, j)  # 標記整個島嶼return count

例題 2：全排列（LeetCode 46）

問題：給定不含重復數字的數組，返回所有可能的全排列。
思路：DFS 回溯法，通過遞歸探索每個位置的可能數字，用 visited 標記已使用的數字，回溯時恢復狀態以嘗試其他組合。
代碼：

def permute(nums):result = []n = len(nums)def backtrack(path, visited):# 終止條件：路徑長度等于數組長度if len(path) == n:result.append(path.copy())returnfor i in range(n):if not visited[i]:# 選擇當前數字visited[i] = Truepath.append(nums[i])# 遞歸下一層backtrack(path, visited)# 回溯：撤銷選擇path.pop()visited[i] = Falsebacktrack([], [False]*n)return result

五、BFS 與 DFS 的區別與適用場景

維度	BFS	DFS
數據結構	隊列（先入先出）	棧 / 遞歸棧（后入先出）
適用場景	最短路徑（無權圖）、層次遍歷、拓撲排序	排列組合、連通性、回溯剪枝、路徑搜索
空間復雜度	較高（取決于最寬層節點數）	較高（取決于遞歸深度）
特點	首次到達目標即最短路徑	可通過回溯剪枝優化效率