一句话总结
BFS 和 DFS 是遍历图 / 树 / 网格的两种基本策略。唯一差别是用队列还是用栈来决定"下一个访问谁"：
🎢
BFS（广度优先）
用队列，一圈一圈向外扩散。首次到达某点的路径就是最短路径（边权相同时）。
🕳️
DFS（深度优先）
用栈 / 递归，一条路走到黑再回头。擅长找连通块、判环、拓扑排序。
🚫
visited 集合
两者都必须有。图有环，不标记已访问就会无限循环 / 指数级重复。
⚖️
复杂度
时间 O(V + E)，空间 O(V)。V 顶点数、E 边数。
一、遍历顺序对比
二、代码模板
2.1 BFS：队列 + visited（无权图最短路）
from collections import deque
def bfs(graph, start):
visited = {start}
q = deque([start])
dist = {start: 0} # 记录到起点的最短距离
while q:
node = q.popleft() # 队首出队（先来的先扩散）
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt) # ★ 入队时就标记，防止重复入队
dist[nxt] = dist[node] + 1
q.append(nxt)
return dist
# 层序遍历写法（需要区分"第几层"时）
def bfs_level(graph, start):
visited, q, level = {start}, deque([start]), 0
while q:
for _ in range(len(q)): # 一次性处理完当前这一层
node = q.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
q.append(nxt)
level += 1
return level
💡 关键细节：必须在入队时就加入 visited，而不是出队时。否则同一节点可能被多个前驱重复入队多次，队列膨胀，复杂度退化。
2.2 DFS：递归 / 显式栈
# 写法一：递归（最简洁，本质是系统调用栈）
def dfs_recursive(graph, node, visited):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs_recursive(graph, nxt, visited)
# 写法二：显式栈（避免递归过深爆栈）
def dfs_iterative(graph, start):
visited, stack = set(), [start]
while stack:
node = stack.pop() # 栈顶出栈（后入先出 → 往深处钻）
if node in visited:
continue
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
stack.append(nxt)
return visited
⚠️ 递归 DFS 的栈溢出：Python 默认递归深度约 1000。图/网格规模大时（如 300×300 的岛屿题）会 RecursionError，此时改用显式栈迭代或
sys.setrecursionlimit(10000)。
三、网格（矩阵）上的 BFS/DFS
3.1 岛屿问题（LeetCode 200）：DFS 洪水填充
def numIslands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if (r < 0 or r >= m or c < 0 or c >= n
or grid[r][c] != '1'): # 越界 or 非陆地 → 返回
return
grid[r][c] = '0' # ★ 就地标记：把陆地"淹成"水，省去 visited 数组
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): # 四个方向
dfs(r + dr, c + dc)
for r in range(m):
for c in range(n):
if grid[r][c] == '1':
count += 1
dfs(r, c) # 淹掉整座岛
return count
四、怎么选：BFS 还是 DFS？
| 场景 | 推荐 | 理由 |
|---|---|---|
| 无权图最短路径 / 最少步数 | BFS | 首次到达即最短，层数就是距离 |
| 二叉树层序遍历 | BFS | 按层输出天然契合队列 |
| 数连通块 / 岛屿 / 洪水填充 | DFS（或 BFS 皆可） | 只需遍历完整块，不关心距离 |
| 判环 / 拓扑排序 | DFS | 需要"后序遍历"和递归栈判断回边 |
| 找所有路径 / 排列组合 | DFS（回溯） | 需要完整走完一条路再回退 |
| 矩阵最长递增路径 | DFS + 记忆化 | 需要子问题结果，DFS 天然支持 |
| 迷宫最短步数 / 单词接龙 | BFS | 求最少变换次数 |
一句话决策：问"最少几步 / 最短多远 / 按层输出" → BFS；问"是否存在 / 有多少个 / 找出所有方案 / 拓扑关系" → DFS。
4.1 复杂度对比
| 维度 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列（FIFO） | 栈（LIFO）或递归 |
| 时间复杂度 | O(V + E) | O(V + E) |
| 空间复杂度 | O(V)（队列最宽一层的规模） | O(V)（递归深度，最坏等于图高） |
| 最短路保证 | ✅ 无权图最短路 | ❌ 不保证 |
| 内存峰值 | 稠密图时队列可能很大 | 深图时栈可能很深 |