BFS 广度优先搜索

2026-06-02

一句话：BFS = 把图当池塘，从起点丢颗石头，看波纹一圈圈扩出去。第一次碰到目标的那一圈，就是最短步数（边权为 1）。

直觉

想象你站在迷宫入口往里喊话。声音不会”挑一条路深入”，而是同时充满当前这一圈空气，再充满下一圈。BFS 就是把声音的扩散过程写成代码：

当前波前（队列里的节点）= 距起点恰好步的所有点
下一波前 = 当前波前的所有邻居（去掉访问过的）
第一次把目标包进波前的那个，就是答案

DFS 是”先一条路走到黑再回头”，BFS 是”齐步走、同时推进”。只要问的是”最少几步”，几乎都是 BFS。

下面动画把这层”波纹”画了出来。点 [开始] 看队列怎么一层层吞掉网格、第几步碰到终点；切到第二个动画，看”多源 BFS”——多颗石头同时丢进池塘，波纹相遇即停。

模板（背这个就够了）

from collections import deque

def bfs(start):
    q = deque([start])
    visited = {start}
    step = 0
    while q:
        for _ in range(len(q)):          # 锁定"当前这一层"的大小
            node = q.popleft()
            if is_target(node):
                return step
            for nxt in neighbors(node):
                if nxt not in visited:
                    visited.add(nxt)     # 入队就标记，不要等到出队！
                    q.append(nxt)
        step += 1                        # 一整层处理完才 +1
    return -1

三个锁死的细节（错一个就 WA 或 TLE）：

for _ in range(len(q)) —— 先把 len(q) 冻住，再循环。否则你边出队边入队，分不清”哪些属于当前层”。
入队时就 visited.add(nxt)，不是出队时。出队时标记，同一个点会被 4 个邻居各塞一次，队列爆炸（动画里看得很清楚：放开这个限制，橙色单元会反复闪）。
step += 1 放在 for 外面，不是里面。step 是层号，不是节点号。

变种

网格 BFS

最常考。neighbors 换成方向数组：

DIRS = [(-1,0),(1,0),(0,-1),(0,1)]   # 上下左右
for dr, dc in DIRS:
    nr, nc = r+dr, c+dc
    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#' and (nr,nc) not in visited:
        ...

多源 BFS

起点不止一个？全部一次性塞进初始队列。等价于在外面挂一个虚拟超级源点，连向每个起点，边权 0。模板一行不改，只改初始化。

1 2	`q = deque(all_starts) visited = set(all_starts)`

经典题：腐烂的橘子（动画 2）、01 矩阵到最近 0 的距离。

0-1 BFS

边权只有 0 和 1。普通队列换成 deque：权 0 走 appendleft，权 1 走 append。O(V+E) 替代 Dijkstra 的 O(E log V)。

双向 BFS

起点终点同时扩散，每轮总是扩较小的一边，两边相遇即返回。搜索空间从砍到，指数减半。条件：终点明确、邻居可反向推。典型题：127 单词接龙、752 转盘锁。

BFS vs DFS 怎么选

最短步数 / 最少操作 → BFS
所有路径 / 排列组合 / 连通块大小 → DFS
拓扑排序 → 都行（Kahn 是 BFS）

经典题

热身：

102. 二叉树层序遍历 —— 最纯粹的 BFS，验证你模板背没背熟
200. 岛屿数量 —— 网格 BFS 求连通块
994. 腐烂的橘子 —— 多源 BFS 原型

进阶：

127. 单词接龙 —— 隐式图 BFS，双向 BFS 提速
752. 打开转盘锁 —— 状态空间 BFS
542. 01 矩阵 —— 反向想：从所有 0 出发的多源 BFS
1293. 网格中的最短路径（消除障碍） —— 状态加一维 (r,c,剩余消除次数)
847. 访问所有节点的最短路径 —— 状态压缩 + BFS

记忆法 & 易错点

记住三个画面就行：

池塘波纹 —— BFS 的本质。第一次碰到目标的波纹半径 = 答案。
冻住的 len(q) —— 区分”这一层”和”下一层”的唯一手段。
入队即标记 —— 不是出队，不是出队，不是出队。

常见坑：

把 step += 1 写到内层 for 里 → 答案变成”访问了几个节点”，错的离谱。
边权不是 1 还用 BFS → 错答案。该上 Dijkstra 或 0-1 BFS。
网格题忘记判断越界 → IndexError 或绕到对面。
求”是否能到达”用 BFS → 没问题但浪费；DFS 写起来更短。只有问最短才必须 BFS。

思考题

为什么 BFS 能保证找到最短路径（边权为 1 时）？

按层扩散，第层的节点离起点的距离恰好是（不会更少：更少的话之前的层就该访问到了；不会更多：相邻层差 1）。第一次访问目标时所在的层数就是最短步数。

"入队时标记" vs "出队时标记" 有什么区别？

入队时标记：每个节点最多入队一次，队列大小 = O(V)。
出队时标记：同一节点可能被多个邻居重复入队（网格里 4 个方向都可能塞同一个点），队列膨胀到 O(E)，时间空间都浪费。结果都对，但后者经常 TLE。

双向 BFS 何时适用？

需要：起点终点都明确 + 邻居能反向推。指数级缩小搜索空间（）。
不适用：终点未知（如”找最远点”）、邻居只能单向（有向图无反图）。