1. 从“一层一层往外扩”说起BFS到底在做什么如果你刷过一阵算法题一定对深度优先搜索DFS和广度优先搜索BFS这两个名字不陌生。很多新手一上来就背模板结果换个题目就不知道怎么套了原因往往是没搞懂 BFS 的本质。我自己的理解是BFS 就好比往池塘里扔一颗石子水波从落点开始一圈一圈向外扩散每一圈到达的位置就是离起点距离相同的一批点。这个“按层扩散”的特性决定了它天生适合解决两类问题——最短路径和最少步数/最少操作次数。那为什么最短路径能用 BFS因为 BFS 按照距离起点由近到远的顺序访问节点第一次访问到某个节点时一定经过了最短的路径在边权相同的情况下。这个结论是很多题目的核心突破口。而 DFS 往往是一条路走到黑更适合解决“是否存在路径”“全排列”“连通性判断”这类问题两者侧重点完全不同。所以你在学 BFS 模板之前先要给自己提个醒拿到一道题如果它要求“最少”“最短”“最快”且状态转移的代价相同第一反应就应该是 BFS而不是 DFS。这个判断一旦错了后面写得再熟练也没用。接下来我会从最基础的队列模板讲起再深入到带状态压缩、二维网格、拓扑排序等变种最后用几道有代表性的例题把完整的思考过程拆开揉碎讲清楚。这篇文章适合刚接触 BFS 的新手也适合刷了一段时间但总觉得“模板背了但不会套”的同学。如果你能完整看完并跟着动手写一遍BFS 这类题基本就稳了。2. BFS 的底层逻辑为什么队列是它的灵魂2.1 队列决定了遍历顺序BFS 的实现核心只有一个数据结构队列。队列的特点是先进先出这正好匹配“先进入第 k 层的节点先扩展出第 k1 层节点”的顺序。每次从队列头部取出一个节点把它所有未访问过的邻居放入队尾这个过程不断重复直到队列为空。我们可以用一个小例子感受一下。假设有一棵二叉树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_setstring或 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 为什么字符串也能用 BFSBFS 不局限于网格和图只要你能定义“从一个状态到下一个状态”的变换规则就能用 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[i1:] 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. 例题四拓扑排序中的 BFSKahn 算法7.1 BFS 不只是用来找最短路径很多初学者以为 BFS 只能处理“走迷宫”类问题其实在图论中BFS 还有一个重要应用是拓扑排序。所谓拓扑排序就是给有向无环图DAG的节点排一个线性顺序使得对每一条有向边 u→vu 都在 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 的坑。
1. 从“一层一层往外扩”说起BFS到底在做什么如果你刷过一阵算法题一定对深度优先搜索DFS和广度优先搜索BFS这两个名字不陌生。很多新手一上来就背模板结果换个题目就不知道怎么套了原因往往是没搞懂 BFS 的本质。我自己的理解是BFS 就好比往池塘里扔一颗石子水波从落点开始一圈一圈向外扩散每一圈到达的位置就是离起点距离相同的一批点。这个“按层扩散”的特性决定了它天生适合解决两类问题——最短路径和最少步数/最少操作次数。那为什么最短路径能用 BFS因为 BFS 按照距离起点由近到远的顺序访问节点第一次访问到某个节点时一定经过了最短的路径在边权相同的情况下。这个结论是很多题目的核心突破口。而 DFS 往往是一条路走到黑更适合解决“是否存在路径”“全排列”“连通性判断”这类问题两者侧重点完全不同。所以你在学 BFS 模板之前先要给自己提个醒拿到一道题如果它要求“最少”“最短”“最快”且状态转移的代价相同第一反应就应该是 BFS而不是 DFS。这个判断一旦错了后面写得再熟练也没用。接下来我会从最基础的队列模板讲起再深入到带状态压缩、二维网格、拓扑排序等变种最后用几道有代表性的例题把完整的思考过程拆开揉碎讲清楚。这篇文章适合刚接触 BFS 的新手也适合刷了一段时间但总觉得“模板背了但不会套”的同学。如果你能完整看完并跟着动手写一遍BFS 这类题基本就稳了。2. BFS 的底层逻辑为什么队列是它的灵魂2.1 队列决定了遍历顺序BFS 的实现核心只有一个数据结构队列。队列的特点是先进先出这正好匹配“先进入第 k 层的节点先扩展出第 k1 层节点”的顺序。每次从队列头部取出一个节点把它所有未访问过的邻居放入队尾这个过程不断重复直到队列为空。我们可以用一个小例子感受一下。假设有一棵二叉树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_setstring或 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 为什么字符串也能用 BFSBFS 不局限于网格和图只要你能定义“从一个状态到下一个状态”的变换规则就能用 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[i1:] 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. 例题四拓扑排序中的 BFSKahn 算法7.1 BFS 不只是用来找最短路径很多初学者以为 BFS 只能处理“走迷宫”类问题其实在图论中BFS 还有一个重要应用是拓扑排序。所谓拓扑排序就是给有向无环图DAG的节点排一个线性顺序使得对每一条有向边 u→vu 都在 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 的坑。
