搜索
本章目标：掌握 BFS、DFS 及其变体（双向 BFS、A*、IDDFS），能解决最短路径和状态空间搜索问题。
你将学到
- BFS 求最短步数
- DFS 找所有解
- 双向 BFS 加速
- A* 启发式搜索
- 迭代加深 IDDFS
1. 概念
搜索算法是在状态空间中寻找目标解的方法。根据探索顺序不同分为：
- BFS（广度优先搜索）：一层一层扩展，天然适合找最短路径（无权图）
- DFS（深度优先搜索）：一条路走到底，适合找所有解或连通性问题
高级搜索策略：
- 双向 BFS：从起点和终点同时搜索，在中间相遇，大幅减少搜索空间
- A 搜索*：带启发函数的优先搜索，用贪心策略引导方向
- 迭代加深 IDDFS：结合 DFS 空间小和 BFS 找最优的特性
搜索的关键是定义状态和状态转移。在网格问题中，状态就是坐标；在复杂问题中，状态可能包含多个变量。
2. 核心模板
BFS 最短路径
python
from collections import deque
def bfs_shortest_path(start, target, get_neighbors):
"""通用 BFS 找最短步数"""
queue = deque([(start, 0)])
visited = {start}
while queue:
state, steps = queue.popleft()
if state == target:
return steps
for neighbor in get_neighbors(state):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return -1 # 不可达DFS 模板
python
def dfs_all_paths(state, target, path, visited, get_neighbors, result):
"""DFS 找所有路径"""
if state == target:
result.append(path[:])
return
for neighbor in get_neighbors(state):
if neighbor not in visited:
visited.add(neighbor)
path.append(neighbor)
dfs_all_paths(neighbor, target, path, visited, get_neighbors, result)
path.pop()
visited.remove(neighbor)双向 BFS
python
def bidirectional_bfs(start, target, get_neighbors):
"""双向 BFS，从两端同时搜索"""
if start == target:
return 0
front = {start}
back = {target}
visited = {start, target}
step = 0
while front and back:
step += 1
# 始终扩展较小的一端
if len(front) > len(back):
front, back = back, front
next_front = set()
for state in front:
for neighbor in get_neighbors(state):
if neighbor in back:
return step + 1 # 两端相遇（或 step，视定义）
if neighbor not in visited:
visited.add(neighbor)
next_front.add(neighbor)
front = next_front
return -1复杂度
- BFS/DFS：时间 O(V + E)，空间 O(V)
- 双向 BFS：时间 O(b^(d/2))，b 为分支因子，d 为解深度
3. 经典题目精讲
LeetCode 127 · 单词接龙
题意：给定起始单词、目标单词和字典，每次变一个字母，求最短变换序列长度。
思路：BFS，每个单词是一个状态，变换一个字母得到邻居。
python
from collections import deque
def ladderLength(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, length = queue.popleft()
if word == endWord:
return length
# 枚举所有可能的变换单词
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in wordSet and new_word not in visited:
visited.add(new_word)
queue.append((new_word, length + 1))
return 0LeetCode 695 · 岛屿的最大面积
题意：给定二维网格，找最大岛屿面积。
思路：DFS/BFS 遍历每个连通区域，计数面积。
python
def maxAreaOfIsland(grid):
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
return 0
grid[r][c] = 0 # 标记已访问
return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
max_area = max(max_area, dfs(r, c))
return max_areaLeetCode 773 · 滑动谜题
题意：2×3 拼图，每步移动一格，求还原到 [[1,2,3],[4,5,0]] 的最少步数。
思路：BFS，把棋盘序列化为元组作为状态。
python
from collections import deque
def slidingPuzzle(board):
target = (1, 2, 3, 4, 5, 0)
# 展平棋盘
start = tuple(board[0] + board[1])
# 每个位置可以移动到的相邻位置
neighbors = {0: [1, 3], 1: [0, 2, 4], 2: [1, 5],
3: [0, 4], 4: [1, 3, 5], 5: [2, 4]}
queue = deque([(start, start.index(0), 0)]) # (状态, 0的位置, 步数)
visited = {start}
while queue:
state, zero_pos, steps = queue.popleft()
if state == target:
return steps
for neighbor_pos in neighbors[zero_pos]:
new_state = list(state)
new_state[zero_pos], new_state[neighbor_pos] = new_state[neighbor_pos], new_state[zero_pos]
new_state = tuple(new_state)
if new_state not in visited:
visited.add(new_state)
queue.append((new_state, neighbor_pos, steps + 1))
return -14. 易错点
- ⚠️ BFS 入队时立即标记 visited，否则可能重复入队
- ⚠️ DFS 递归深度过大可能栈溢出，需改为迭代
- ⚠️ 双向 BFS 相遇时返回的步数需要仔细计算（根据状态定义）
- ⚠️ 状态序列化要保证唯一性，元组比列表适合做字典 key
5. 推荐刷题清单
| 题号 | 题名 | 难度 | 关键 |
|---|---|---|---|
| 127 | 单词接龙 | Hard | BFS |
| 200 | 岛屿数量 | Medium | DFS/BFS |
| 695 | 岛屿的最大面积 | Medium | DFS |
| 787 | K 站中转内最便宜航班 | Medium | Bellman-Ford/BFS |
| 773 | 滑动谜题 | Hard | BFS 状态搜索 |
延伸阅读
- LeetCode 官方
- 代码随想录
- 《算法导论》(CLRS) 第 22 章