BFS是最短路径的保证，层序遍历、岛屿计数、单词接龙的核心算法
广度优先搜索（BFS, Breadth-First Search）从起点出发，逐层向外扩展，先访问距离近的节点，再访问距离远的。BFS 的核心特性是最短路径保证——在无权图中，BFS 第一次到达目标节点的路径一定是最短的。BFS 用队列实现，时间复杂度 O(V+E)。
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)| 变体 | 特点 | 示例 |
|---|---|---|
| 标准BFS | 找最短路径 | LC 1091, LC 127 |
| 层序BFS | 按层记录，区分层级 | LC 102, LC 515 |
| 多源BFS | 多个起点同时扩展 | LC 1162, LC 542 |
| 双向BFS | 从两端同时搜索 | LC 127 优化 |
题目描述：给你二叉树的根节点 root，返回其节点值的层序遍历。
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
from collections import deque
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
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时间复杂度：O(n)
空间复杂度：O(w)
题目描述：字典 wordList 中从 beginWord 到 endWord 的最短转换序列的长度。每次转换只能改变一个字母，转换后的单词必须在字典中。
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
from collections import deque, defaultdict
if endWord not in wordList:
return 0
# 预处理: 通配符 → 单词列表
adj = defaultdict(list)
for word in wordList + [beginWord]:
for i in range(len(word)):
pattern = word[:i] + '*' + word[i+1:]
adj[pattern].append(word)
# BFS
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in range(len(word)):
pattern = word[:i] + '*' + word[i+1:]
for neighbor in adj[pattern]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return 0时间复杂度：O(M² × N)
空间复杂度：O(M² × N)
题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿是被水包围的陆地，由相邻的陆地连接而成。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
from collections import deque
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
# BFS 淹没该岛屿
queue = deque([(r, c)])
grid[r][c] = '0'
while queue:
row, col = queue.popleft()
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
grid[nr][nc] = '0'
queue.append((nr, nc))
return count时间复杂度：O(m×n) — 每个格子最多访问一次
空间复杂度：O(min(m,n)) — BFS 队列最大长度
BFS 还有一些进阶技巧，掌握后可以解决更复杂的搜索问题。
从起点和终点同时搜索，当两端的搜索树相遇时找到最短路径。搜索空间从 O(b^d) 降到 O(2×b^(d/2))，指数级优化！
def bidirectional_bfs(begin, end, graph):
front = {begin}
back = {end}
visited = {begin, end}
steps = 0
while front and back:
# 始终从较小的集合扩展
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 steps + 1
if neighbor not in visited:
visited.add(neighbor)
next_front.add(neighbor)
front = next_front
steps += 1
return -1多个起点同时入队，适用于"到最近源的距离"类问题。所有源同时开始扩展，第一次到达某个格子时的距离就是到最近源的距离。