1. 从“一层一层往外扩”说起：BFS到底在做什么
如果你刷过一阵算法题，一定对深度优先搜索（DFS）和广度优先搜索（BFS）这两个名字不陌生。很多新手一上来就背模板，结果换个题目就不知道怎么套了，原因往往是没搞懂 BFS 的本质。我自己的理解是：BFS 就好比往池塘里扔一颗石子，水波从落点开始一圈一圈向外扩散；每一圈到达的位置，就是离起点距离相同的一批点。这个“按层扩散”的特性，决定了它天生适合解决两类问题——最短路径和最少步数/最少操作次数。
那为什么最短路径能用 BFS？因为 BFS 按照距离起点由近到远的顺序访问节点，第一次访问到某个节点时，一定经过了最短的路径（在边权相同的情况下）。这个结论是很多题目的核心突破口。而 DFS 往往是一条路走到黑，更适合解决“是否存在路径”“全排列”“连通性判断”这类问题，两者侧重点完全不同。
所以，你在学 BFS 模板之前，先要给自己提个醒：拿到一道题，如果它要求“最少”“最短”“最快”且状态转移的代价相同，第一反应就应该是 BFS，而不是 DFS。这个判断一旦错了，后面写得再熟练也没用。
接下来，我会从最基础的队列模板讲起，再深入到带状态压缩、二维网格、拓扑排序等变种，最后用几道有代表性的例题把完整的思考过程拆开揉碎讲清楚。这篇文章适合刚接触 BFS 的新手，也适合刷了一段时间但总觉得“模板背了但不会套”的同学。如果你能完整看完并跟着动手写一遍，BFS 这类题基本就稳了。
2. BFS 的底层逻辑：为什么队列是它的灵魂
2.1 队列决定了遍历顺序
BFS 的实现核心只有一个数据结构：队列。队列的特点是先进先出，这正好匹配“先进入第 k 层的节点，先扩展出第 k+1 层节点”的顺序。每次从队列头部取出一个节点，把它所有未访问过的邻居放入队尾，这个过程不断重复，直到队列为空。
我们可以用一个小例子感受一下。假设有一棵二叉树：
1 / \ 2 3 / \ \ 4 5 6如果用 BFS 遍历，顺序是 1 → 2,3 → 4,5,6。具体过程：
- 队列初始只有节点 1；
- 取出 1，把它的左右孩子 2、3 入队；
- 取出 2，把 4、5 入队；此时队列是 3、4、5；
- 取出 3，把 6 入队；
- 依次取出 4、5、6，它们没有孩子，队列最终为空。
你会发现，队列中始终是“当前层 + 下一层”的混合，但取出节点的顺序永远是当前层全部取完，才开始下一层。这个特性就是“层”的来源。
2.2 为什么第一次访问就是最短路径
这是一个很关键但容易被忽略的点。在边权相等（例如每个格子移动一步的代价都是 1）的图中，BFS 从起点出发，第一轮遍历的是距离为 1 的所有节点，第二轮是距离为 2 的所有节点，依此类推。因此，当某个节点第一次被加入队列时，它的“层数”就是它距离起点的最短距离。之后即使再从其他路径访问到它，路径也不会更短了，所以通常我们会用一个visited数组标记已经访问过的节点，避免重复入队，也避免重复计算。
注意：这个结论的前提是所有边的权重相等。如果边权不同，比如走一步消耗 2、另一条路走一步消耗 1，那么第一次访问未必是最优的，此时应该考虑 Dijkstra 算法，而不是裸 BFS。这算是 BFS 模板最容易踩的坑之一。
2.3 BFS 的复杂度怎么看
在普通图/网格中，BFS 的时间复杂度是 O(V + E)，V 是节点数，E 是边数。比如一个 m×n 的网格，节点数 mn，每个节点最多有 4 个邻居，所以边数大约是 2mn，总复杂度 O(mn)。空间复杂度主要来自于队列和 visited 数组，同样是 O(V)。
如果你遇到的是状态空间巨大的问题（比如 15 数码、魔方），BFS 的队列可能会爆炸，这时就需要考虑双向 BFS、A* 或状态压缩优化。后文例题里会涉及双向 BFS 的写法，那是处理大状态空间的实用技巧。
3. 通用 BFS 模板：从伪代码到实战写法
3.1 最朴素、最通用的三层结构
无论题目怎么变，BFS 的骨架通常就三块：
- 初始化队列和 visited 标记；
- 将起始状态入队并标记；
- 循环：取出队首，判断是否为目标，扩展邻居，合法且未访问的入队。
我用伪代码写一下：
queue = [] visited = set() # 或数组/哈希表 queue.push(start) visited.add(start) step = 0 while queue 非空: size = queue.size() for i in 0..size-1: # 只处理当前层的节点 cur = queue.pop() if cur 是目标: return step for nxt in 根据规则扩展(cur): if nxt 合法 and nxt not in visited: visited.add(nxt) queue.push(nxt) step += 1 return -1 # 表示无解这里特别强调size的用法。如果我们想知道最短路径的长度，就必须知道每一层的边界。每轮循环开始时，先记录当前队列长度size，然后只把size个节点当作“本层”处理完，下一次循环再自然进入下一层。如果不这么做，会把不同层的节点混在一起，步数就会算错。这个细节我在面试辅导和给同学讲题时被反复问到，很多人模板背得滚瓜烂熟，一遇到“求最小步数”就出错，基本都是没写size分层。
3.2 如何优雅记录步数
记录步数有两种常用方式：
- 全局 step + 按层循环：如上面的伪代码，每次处理完一整层后
step++，返回时就是当前层数。 - 入队时携带步数：队列存
(节点, 距离)，扩展邻居时距离 +1。好处是不用关心层的边界，但空间开销略大，且在某些复杂状态（如位压缩）中不太方便。
我一般推荐第一种，因为它不仅省空间，也更符合“层”的语义。尤其当你需要同时求“最短路径经过哪些节点”时，还可以在第一种基础上加一个parent数组，记录每个节点是从哪个方向来的，最后反向回溯。
3.3 visited 标记的三种形态
visited的选型直接决定整个算法的效率和代码复杂度，我在不同题目里总结出三种常见形态：
- 数组：适用于节点是连续的整数编号，比如编号 0~n-1 的图。直接用
bool visited[n]。 - 哈希表 / 集合：适用于节点是字符串、坐标对、自定义对象。例如八数码中的棋盘状态
"12345678x"，用unordered_set<string>或 Python 的set最方便。 - 二维/三维数组：适用于网格、迷宫。如
bool vis[m][n]，或三维vis[x][y][state]表示在 (x,y) 位置并且处于某种状态（比如已经拿到了某把钥匙）。
这里再分享一个小技巧：如果状态空间很大，visited除了标记是否访问，还可以顺便存“距离”。比如用dist[x][y]，初始化成 -1，访问过就赋值为具体距离。这样既起到了标记作用，又能在需要时直接读取最短距离，一举两得。
3.4 常用的方向数组与坐标技巧
在二维网格类 BFS 里，我们经常会写一个方向数组：
dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]然后循环四次：
for i in 0..3: nx = x + dx[i] ny = y + dy[i] if 0 <= nx < m and 0 <= ny < n and 未访问: 处理这个模板几乎可以解决所有“走格子”题目。需要注意边界判断一定要先做，否则数组会越界。很多新手喜欢在循环里写一堆if分支，不如方向数组干净。如果你做的是“八个方向”的题（例如地图寻路），只需要把方向数组扩展成 8 组即可。
4. 例题一：二维网格中的最短路径（走迷宫）
4.1 题目场景
我们先从最经典的迷宫走法入手。假设有一个m×n的网格，0表示可以走，1表示障碍物。给定起点(sr, sc)和终点(tr, tc)，每次可以上下左右移动一格，问从起点到终点的最短路径长度（步数）。如果无法到达，返回 -1。
这个问题几乎是所有 BFS 迷宫的母题。面试中经常出现，甚至有些公司会要求你“不用递归实现”或者“用栈/队列分别实现”。掌握它的标准写法后，像“腐烂的橘子”“岛屿数量”“单词梯”这类衍生题都能举一反三。
4.2 完整实现（Python 风格，但思路通用）
from collections import deque def shortestPath(grid, sr, sc, tr, tc): m, n = len(grid), len(grid[0]) if grid[sr][sc] == 1 or grid[tr][tc] == 1: return -1 visited = [[False] * n for _ in range(m)] visited[sr][sc] = True q = deque() q.append((sr, sc)) steps = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while q: size = len(q) for _ in range(size): x, y = q.popleft() if x == tr and y == tc: return steps for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0 <= nx < m and 0 <= ny < n: if not visited[nx][ny] and grid[nx][ny] == 0: visited[nx][ny] = True q.append((nx, ny)) steps += 1 return -1很多人会问：为什么要在入队时就标记visited，而不是出队时标记？原因是，如果不入队就标记，同一个节点可能被多个当前层的节点重复加入队列，导致队列膨胀，甚至出现死循环或步数错乱。标记的时机一定要和入队保持一致，这是 BFS 最容易出 bug 的地方。
4.3 从这道题延伸出去的变体
这道题有很多常见的变体，我按难度排个序：
- 如果求的是“从起点到所有点的最短距离”，只需要在 BFS 过程中记录
dist数组，最后遍历所有不为 -1 的点。 - 如果要求“输出最短路径的具体路径”，需要额外维护
pre数组，记录每个点是从哪个点走来的，BFS 结束后从终点反向回溯。 - 如果网格中有多个起点、多个终点，比如“多源 BFS”问题，最典型的就是腐烂的橘子：一开始把所有坏橘子都入队，层数就是分钟数。
- 如果允许“破墙一次”，就需要在 visited 里多增加一维状态，比如
visited[x][y][1]表示已经破过墙。这就是状态空间变成三维的典型例子。
5. 例题二：字符串状态转换的最少操作次数（单词梯）
5.1 为什么字符串也能用 BFS
BFS 不局限于网格和图，只要你能定义“从一个状态到下一个状态”的变换规则，就能用 BFS 求最短路径。最经典的例子就是单词梯：给定一个开始单词、一个结束单词和一个词典，每次只能改变单词中的一个字母，且改变后的单词必须在词典中，问从开始单词到结束单词最少需要几步。
这个问题的状态就是“当前单词”，每个单词可以通过改变任意位置的一个字母生成多个邻居。如果把每个单词看成节点、合法变换看成边，那么求最少变换次数就等价于求无权图上的最短路径。
5.2 一个高效的实现思路
最直观的做法是：对于当前单词的每个位置，尝试把该位置的字符替换成a~z，如果新词在词典中且没访问过，就入队。这个算法的复杂度是 O(单词长度 × 26 × 队列长度)，在大多数题目里够用。如果词典很大，可以先将词典放入一个哈希集合，这样判断是否存在是 O(1)。
我写一个伪代码：
wordSet = set(wordList) if endWord not in wordSet: return 0 q = deque([beginWord]) visited = {beginWord} step = 1 while q: size = len(q) for _ in range(size): word = q.popleft() if word == endWord: return step for i in range(len(word)): for c in 'abcdefghijklmnopqrstuvwxyz': newWord = word[:i] + c + word[i+1:] if newWord in wordSet and newWord not in visited: visited.add(newWord) q.append(newWord) step += 1 return 0这里有个容易忽略的细节：变换后的单词自己也可能出现在词典中，包括 beginWord 本身。如果词典里包含 beginWord，一般不需要特殊处理，只要标记了 visited 就不会重复访问。另外，如果题目允许“一个单词可以多次使用”，那就不叫 BFS 最短路径了，问题性质就变了，现实题目里几乎都默认每个单词只能用一次。
5.3 状态空间爆炸时：双向 BFS
当单词长度较长、词典较大时，从 beginWord 往 endWord 扩展的层数可能很深，队列规模会呈指数级增长。这时候用“双向 BFS”常常能大幅减少扩展次数。思路是：从 beginWord 和 endWord 同时开始 BFS，每次扩展层数较小的一边，当两边访问过的状态有交集时，说明找到了一条路径。
双向 BFS 的最小距离计算公式是答案 = 从起点到交点的步数 + 从终点到交点的步数，但因为层数是逐步增长的，具体实现时需要维护两个队列和两个 visited 集合，每轮扩展一层，然后检查是否有交集。很多经验丰富的选手喜欢用这种写法处理“十五数码”“单词梯”等题目，实测下来效率提升明显。我建议大家在写好单向 BFS 之后，找个题目练一练双向 BFS，这是从入门到进阶的一个重要台阶。
6. 例题三：带状态压缩的 BFS（钥匙与门）
6.1 为什么需要状态压缩
有些题目中，你在图中的位置并不是唯一决定状态的因素，还带着“当前收集到了哪些物品/钥匙”。比如有一个迷宫，里面有若干钥匙和若干扇门，每扇门需要对应的钥匙才能打开，问从起点到终点最少需要多少步。
如果只用二维坐标做 visited，会出现一个问题：你先走到了某个位置，但因为当时没有钥匙，无法进入某个区域；之后你拿到了钥匙，想再回到这个位置进入新区域，却发现它已经标记为 visited，于是被错误地拦住了。所以 visited 必须额外加上“当前拥有钥匙的集合”这个维度。
由于钥匙数量通常不超过 10 把，我们可以用一个整数的二进制位表示拥有哪些钥匙。比如state的第 k 位为 1 表示拥有第 k 把钥匙。这样状态就变成了(x, y, state)，对应一个三维 visited 数组，大小是m × n × (1 << keyCount)，完全可控。
6.2 关键代码片段
def bfs(grid): m, n = len(grid), len(grid[0]) # 统计所有钥匙，记录起点 key_count = 0 start = None for i in range(m): for j in range(n): if 'a' <= grid[i][j] <= 'z': key_count += 1 if grid[i][j] == '@': start = (i, j) full_state = (1 << key_count) - 1 visited = [[[False] * (1 << key_count) for _ in range(n)] for _ in range(m)] visited[start[0]][start[1]][0] = True q = deque() q.append((start[0], start[1], 0, 0)) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while q: x, y, state, step = q.popleft() if state == full_state: return step for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != '#': cell = grid[nx][ny] nState = state if 'a' <= cell <= 'z': nState |= (1 << (ord(cell) - ord('a'))) if 'A' <= cell <= 'Z': door = 1 << (ord(cell) - ord('A')) if not (nState & door): continue if not visited[nx][ny][nState]: visited[nx][ny][nState] = True q.append((nx, ny, nState, step + 1)) return -1这段代码有几个点要注意：
- 遇到门时，要先判断当前位置的
state里是否有对应钥匙，如果没有，直接跳过该方向。注意要先计算新的状态，因为可能这一格本身就是钥匙，但门的判断用旧状态，所以这里我先把钥匙位更新到nState，再检查门，这是一种取巧但安全的写法。 - visited 的第三维是
state，同一个坐标在不同钥匙组合下会被视为不同状态，因此可以重复入队，这是解决“先到但没钥匙”问题的核心。 - 终点可能是任意位置，不一定是出口，所以结束条件是
state == full_state，表示收集完所有钥匙，这个时候返回步数即可。
这种“状态压缩 + BFS”的模式还可以扩展到很多场景，比如“带着不同速度/装备”“持有不同颜色的染色状态”等。理解了一维状态表示，遇到复杂状态时你就有了解题方向。
7. 例题四：拓扑排序中的 BFS（Kahn 算法）
7.1 BFS 不只是用来找最短路径
很多初学者以为 BFS 只能处理“走迷宫”类问题，其实在图论中，BFS 还有一个重要应用是拓扑排序。所谓拓扑排序，就是给有向无环图（DAG）的节点排一个线性顺序，使得对每一条有向边 u→v，u 都在 v 之前。典型场景包括课程先修安排、任务调度、依赖关系构建等。
Kahn 算法本质上就是 BFS 思路：先找出所有入度为 0 的节点，作为起点放入队列；然后不断取出节点，把它指向的邻居节点的入度减 1，当某个邻居的入度变成 0 时，将它入队。如果最终入队的节点数等于总节点数，说明图中无环，拓扑排序成功；否则说明存在环。
7.2 一个课程安排的例子
假设有 n 门课程，编号 0~n-1，给定一组先修关系[ai, bi]表示学习课程ai之前必须先学习bi。问是否可能学完所有课程，如果可能，给出一组学习顺序。
实现思路：
from collections import deque def findOrder(n, prerequisites): indegree = [0] * n graph = [[] for _ in range(n)] for a, b in prerequisites: graph[b].append(a) indegree[a] += 1 q = deque([i for i in range(n) if indegree[i] == 0]) order = [] while q: cur = q.popleft() order.append(cur) for nxt in graph[cur]: indegree[nxt] -= 1 if indegree[nxt] == 0: q.append(nxt) if len(order) == n: return order else: return []这里我用了数组graph存储邻接表，indegree记录每个节点的入度。注意判断“是否能完成”的条件是order的长度是否等于n，如果小于 n，说明有环，那些环上的节点永远无法让入度变成 0。
拓扑排序中的 BFS 和普通 BFS 的区别在于：普通 BFS 的起点通常是单一的，而拓扑排序的起点是“所有入度为 0 的节点”，而且扩展时要维护入度。这个模板在“课程表”“项目管理”“编译依赖顺序”等题里都适用，建议单独整理进模板库。
8. 常见问题与排查技巧实录
8.1 为什么我的 BFS 死循环或者超时？
死循环的常见原因是没有正确标记 visited，或者标记时机晚了一步。还有一种隐蔽情况是：在扩展邻居时，忘记了“当前状态”和“下一个状态”的区分。比如在状态压缩的题目里，如果在到达新位置后改变了 state，又用改变后的状态去判断visited，但后续同一位置的不同状态被反复入队，就可能导致指数级增长。
超时的原因往往是没有剪枝或没有用 visited 去重。网格类题目如果每个点都可以反复走，那就必须用 visited 防止回头；但如果状态空间本身就很大，比如某些棋盘题，建议改用双向 BFS 或者 A*。
8.2 如何定位步数多一层或少一层的问题
这个 bug 非常经典。错误的表现是答案比正确答案多 1 或少 1。多 1 通常是因为在起点时就执行了step++，少 1 则往往是没有在取出目标节点时立刻返回，而是等这一层全部处理完才返回。
我的建议是：把 step 增加放在“一层处理完后”而不是“入队后”，并在取到目标时立刻return，不要等到循环结束。如果你不确定，可以先用一个极简例子手动模拟：起点和目标相邻，正确的步数应该是 1。
8.3 队列该用deque还是普通数组？
在 Java 里可以用ArrayDeque，在 C++ 里可以用queue，在 Python 里必须用collections.deque。很多 Python 新手直接用 list 当队列，用pop(0)出队，这个操作是 O(n) 的，当队列很长时会让整体复杂度退化到 O(n^2)，非常致命。一定要使用deque的popleft()。
8.4 如何判断一道题能不能用 BFS？
我总结了三个条件：
- 状态之间有明确的转移关系，且转移代价恒定；
- 需要求最短/最少/最快等最优值；
- 状态空间在可接受范围内。
如果转移代价不同，可以先考虑 Dijkstra 或 0-1 BFS；如果状态空间极大且能找到一个启发式函数，可以尝试 A*；如果只有两个端点，双向 BFS 往往能救命。这些判断要在做题时形成条件反射，而不是等代码写完才发现不对劲。
9. 我的一点个人体会与模板整理建议
刷了这么多年题，教过不少同学，我对 BFS 最深的一点感受是：模板只是骨架，真正的功夫在于“状态定义”。BFS 题目千变万化，但绝大多数都能归为三类——网格坐标、字符串/序列状态、图上的节点状态。每一种状态都对应一种 visited 的写法：二维数组、哈希集合、状态压缩数组。只要你能把“一个节点/一种状态”定义清楚，剩下的就是套模板。
我自己的做法是，在本地维护一个 BFS 模板文件，按类别分几个函数：
bfs_grid(grid, start, end)bfs_string(start, end, wordSet)bfs_with_state(grid, start, keyCount)topological_sort(n, edges)
每次遇到新题，先匹配类别，再针对题目修改扩展规则和 visited 定义。这样既避免了从零开始写，也降低了写错的概率。建议你也建立这样一个自己的模板库，可以在刷题过程中不断补充和精修。
另外，想再强调一个容易被忽视的点：BFS 的代码在面试或比赛中“写对”的优先级远高于“写快”。因为 BFS 的 bug 往往很隐蔽，稍微漏掉一个 visited 标记或者把步数算错，整个题目就废了。我见过太多人上来就噼里啪啦写代码，结果越写越乱。更稳妥的顺序是：先在草稿上画出状态转移图，确认每个状态如何扩展、边界是什么、什么时候算到达目标，再动手写代码。看似多花了一两分钟，实际省下的是无限调 bug 的时间。
如果你能把上面这些模板和例题真正吃透，再遇到 BFS 题目，大概率不会再出现“不知道怎么下手”的情况。希望这篇总结对你的算法进阶有帮助，也欢迎你在评论区交流那些自己踩过的 BFS 的坑。
