★ FEATURED ARTICLE 很多同学学 BFS 模板第一反应就是背代码。我也这么干过背完发现换个题目照样不会写。问题出在哪儿你背的是那几行队列操作却没搞懂 BFS 真正在做什么。我刷了上百道搜索题之后把 BFS 的模板固定成了一句话用队列保住遍历顺序用 visited 挡住回头路一层一层往外扩散直到碰到目标。这篇文章就把这句话拆开揉碎从模板到例题给你讲明白。如果你是刚接触算法的新手这篇文章能让你少走弯路如果你已经会写几道 BFS 题我也建议你看看最后一章的实战细节那是我踩坑踩出来的经验。1. 从最短路径这个关键词理解 BFS 的底层逻辑1.1 为什么 BFS 能找到最短路径BFS 全称是广度优先搜索它的搜索方式像水波纹一样从一个起点向外一圈一圈扩散。第一圈覆盖距离为 1 的所有点第二圈覆盖距离为 2 的所有点依此类推。由于这个一圈一圈的特性当我们第一次遇到目标节点时当前所在的圈数一定是最小的步数。这是 DFS 做不到的。举个最直白的例子你在一个迷宫里找出口一条路走到黑DFS可能走很久才发现走错了然后回头换路。而 BFS 的做法是把所有可能走一步就能到达的位置都看一遍再把走两步能到达的位置都看一遍……直到出口出现。第一次发现出口时的层数就是从起点到出口的最短距离。这里面有一个关键前提每一步的代价必须是相同的。BFS 默认每走一步都是等权重的如果某一步代价是 2某一步代价是 1那 BFS 找出来的最短步数就不一定是最短路径。这种带权最短路径问题需要交给 Dijkstra 或者 A*不要硬套 BFS。1.2 队列和 visited缺一不可BFS 依赖两个核心结构队列和访问标记。队列用来保证遍历顺序。因为队列是先进先出FIFO先被发现的节点会先被扩展这恰好符合逐层扩散的需求。如果换成栈那就变成了深度优先搜索。visited 用来防止重复访问。理论上如果不加 visitedBFS 会在环形的图里无限循环或者在网格图里来回走重复格子。加 visited 之后每个节点最多被访问一次时间复杂度就从指数级爆炸降到了节点总数乘以每个节点的邻居数。你可能见过有些人写 BFS 时不用 visited而是直接修改原数组的值。比如把已经走过的格子从 0 改成 1。这种原地标记的技巧在某些题里能省内存但有个隐患如果你还需要保留原始数据或者遍历过程中需要重新访问那个格子就会出错。所以我更推荐单独维护一个 visited 数组或者 set思路清晰调试也方便。1.3 BFS 与 DFS 的快速对比对比维度BFSDFS数据结构队列栈或递归栈空间复杂度通常为 O(节点数/层宽)通常为 O(深度)最短路径能直接找到需要遍历所有路径后比较适用场景最小步数、最短距离、层级扩散连通性检查、回溯、拓扑排序、路径枚举实现难度模板固定理解后不易错递归写法简洁但容易栈溢出一个常见的误解是BFS 空间复杂度一定比 DFS 高。其实不一定。在二叉树这种层宽和深度都小的结构里两者差不多但在一个很深的链式图里BFS 的空间会远大于 DFS。所以选哪种搜索要看题目限制。2. 一套可以直接抄作业的 BFS 模板2.1 模板骨架Python我把 BFS 的写法固定成下面这个模板它可以应对 90% 以上的 BFS 题from collections import deque def bfs(start, target): queue deque([start]) visited set([start]) step 0 while queue: # 每一层统一处理step 代表当前扩散到了第几层 for _ in range(len(queue)): node queue.popleft() if node target: return step # 生成所有相邻节点具体逻辑由题目决定 for neighbor in get_neighbors(node): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) step 1 return -1 # 没找到这个模板的核心只有四步初始化把起点放入队列并标记为已访问。层内遍历用len(queue)圈出当前层的节点逐个处理。出口检查如果当前节点就是目标直接返回当前步数。扩散把当前节点所有合法的邻居加入队列并标记已访问。get_neighbors是模板里唯一需要根据题目大量修改的部分。它负责告诉 BFS从当前节点可以走到哪些节点。这一步写错了整个搜索范围就错了。2.2 方向数组与边界处理网格类题目几乎是最常见的 BFS 场景。比如给你一个二维矩阵0 表示空地1 表示障碍求从左上角到右下角的最短路径。这种题目的get_neighbors写法非常固定def get_neighbors(grid, x, y): directions [(1, 0), (-1, 0), (0, 1), (0, -1)] rows, cols len(grid), len(grid[0]) result [] for dx, dy in directions: nx, ny x dx, y dy # 边界检查 可行性检查 if 0 nx rows and 0 ny cols and grid[nx][ny] 0: result.append((nx, ny)) return result这里有两个容易踩的坑偏移量写错(1, 0)是向下(-1, 0)是向上(0, 1)是向右(0, -1)是向左。新手经常把(0, -1)和(0, 1)搞反导致搜索方向偏离。边界检查一定要写在访问数组之前先判断nx和ny是否越界再访问grid[nx][ny]。很多运行时错误都是数组越界导致的。如果矩阵很大使用二维列表做 visited 比 set 更快visited [[False] * cols for _ in range(rows)]二维数组访问是 O(1)而 set 存储元组会有哈希开销。虽然两者都能 AC但在极限数据下二维数组明显更稳。2.3 从图到状态空间BFS 的节点不一定是坐标很多题目初看跟图没有任何关系但数据范围很小适合用 BFS 做状态空间搜索。这时候节点不是网格坐标而是一个完整的状态。比如密码锁问题每个状态是四位数字比如0000。每次操作可以把某一位加一或减一得到一个新状态。这个状态空间一共有 10000 个节点每个节点有 8 个邻居完全可以用 BFS 找从0000到目标状态的最短操作次数。在这种题目里visited不再是二维数组而是一个set存储的是状态字符串。get_neighbors需要自己实现状态的变换逻辑。这种抽象能力才是 BFS 真正考察的地方。3. 四道例题把模板用活3.1 例题一二进制矩阵中的最短路径题目描述给你一个n x n的二进制矩阵grid0表示可以通过1表示障碍。从左上角(0, 0)出发每次可以往八个方向移动一步上、下、左、右、对角求到达右下角(n-1, n-1)的最短路径长度。如果无法到达返回-1。这道题是网格 BFS 的入门经典。八个方向意味着directions里要有 8 个偏移量同时要注意起点本身可能就是障碍。from collections import deque def shortest_path_in_grid(grid): n len(grid) if grid[0][0] 1 or grid[n-1][n-1] 1: return -1 directions [ (1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1) ] queue deque([(0, 0)]) visited [[False] * n for _ in range(n)] visited[0][0] True step 1 # 起点算第 1 步 while queue: for _ in range(len(queue)): x, y queue.popleft() if x n - 1 and y n - 1: return step for dx, dy in directions: nx, ny x dx, y dy if ( 0 nx n and 0 ny n and not visited[nx][ny] and grid[nx][ny] 0 ): visited[nx][ny] True queue.append((nx, ny)) step 1 return -1这里有个小细节step初始值设为 1因为起点本身就算一步。如果题目要求的是走了几步而不是经过多少个节点你可能需要把初始值调成 0。我建议在写代码前先明确题目要返回什么否则很容易差 1。八方向 BFS 的复杂度是 O(n²)因为每个格子最多入队一次。如果不限制方向而是让你在迷宫里任意移动思路完全一样只是 directions 不同。3.2 例题二多源腐烂问题题目描述一个二维网格里2代表腐烂的橘子1代表新鲜橘子0代表空位。每分钟腐烂橘子会感染上下左右相邻的新鲜橘子。求最少经过多少分钟所有橘子都腐烂。如果无法全部腐烂返回-1。这道题和单源 BFS 最大的区别是起点不止一个。所有初始腐烂的橘子同时开始扩散。很多同学会陷入一个误区对每个腐烂橘子单独做一次 BFS然后取最小值。这个做法复杂度太高而且逻辑混乱。正确方式是**【多源 BFS】**先把所有腐烂橘子一次性入队然后一层一层扩散。因为所有源头是同时行动的层数正好就是分钟数。from collections import deque def oranges_rotting(grid): rows, cols len(grid), len(grid[0]) queue deque() fresh_count 0 for i in range(rows): for j in range(cols): if grid[i][j] 2: queue.append((i, j)) elif grid[i][j] 1: fresh_count 1 if fresh_count 0: return 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] minutes 0 while queue: for _ in range(len(queue)): x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if ( 0 nx rows and 0 ny cols and grid[nx][ny] 1 ): grid[nx][ny] 2 fresh_count - 1 queue.append((nx, ny)) minutes 1 return minutes - 1 if fresh_count 0 else -1注意最后返回值minutes - 1。因为最后一轮扩散后queue会变空但minutes在while循环末尾又加了一次。如果你把minutes初始化为-1循环内直接返回会更直观。这个细节在不同写法里有不同处理我建议你用一组简单用例自己在纸上推一遍。顺便说一下这道题里我直接修改了grid[nx][ny] 2作为 visited 标记。因为题目不再需要原始网格这样省去了额外的 visited 数组。但如果网格数据后续还要用就别这么做。3.3 例题三四位数转盘锁问题题目描述有一个四位密码锁初始为0000。每次可以把其中一位向上拨或向下拨一位。0向下拨变成9向上拨变成1。给定一个目标密码和一个死亡密码列表拨动过程中任何状态都不能落在死亡列表里。求从初始状态到目标状态的最少拨动次数如果无法到达返回-1。这道题的难点在于把状态空间想清楚。节点是 10000 个字符串从一个节点出发可以到达 8 个邻居。为什么要用 BFS因为要找最少拨动次数而且每一步代价相同。下面是基于模板的解法from collections import deque def open_lock(deadends, target): dead_set set(deadends) if 0000 in dead_set: return -1 queue deque([0000]) visited set([0000]) step 0 while queue: for _ in range(len(queue)): state queue.popleft() if state target: return step for i in range(4): for delta in (1, -1): # 对第 i 位数字做旋转 new_digit (int(state[i]) delta) % 10 new_state state[:i] str(new_digit) state[i1:] if new_state not in dead_set and new_state not in visited: visited.add(new_state) queue.append(new_state) step 1 return -1这里的get_neighbors不是写成一个独立函数而是直接在循环里生成。注意(int(state[i]) delta) % 10这一行9 1 1010 % 10 00 - 1 -1在 Python 里-1 % 10 9。所以这一行同时处理了向上和向下的回绕非常优雅。这道题如果不用 visited搜索空间会是指数级爆炸。用 visited 后每个状态最多访问一次复杂度 O(10000 * 8)完全在可控范围内。实际刷题时这类小范围状态空间的题目很多只要看到数据范围在 10^4 到 10^6 以内并且要求最短步数优先考虑 BFS。3.4 例题四单词接龙双向 BFS 的经典场景题目描述给定一个起始单词、一个结束单词和一个单词表每次只能改变一个字母且改变后的单词必须在单词表中求从起始单词到结束单词的最短转换序列长度。如果不存在返回 0。这道题标准 BFS 也能做每个单词的邻居是单词表中所有与其相差一个字母的单词。但单词表可能很大如果对每个单词都遍历整个单词表找邻居复杂度很高。更常见的预处理是对于每个单词把它替换成通配符模式例如hit对应[*it, h*t, hi*]然后反向索引。单向 BFS 另一个问题是搜索空间呈指数增长。假设每个节点平均有 30 个邻居深度为 10那要扩展的节点数就是 30^10这太大了。所以这道题更好的做法是双向 BFS从起点和终点同时开始搜索每次选择当前层数较小的一边扩展。当两个方向的 visited 出现交集时就找到了最短路径。from collections import deque def ladder_length(begin_word, end_word, word_list): word_set set(word_list) if end_word not in word_set: return 0 left_queue deque([begin_word]) right_queue deque([end_word]) left_visited set([begin_word]) right_visited set([end_word]) step 1 # 生成所有通配符模式 def get_neighbors(word): result [] for i in range(len(word)): for c in abcdefghijklmnopqrstuvwxyz: if c ! word[i]: new_word word[:i] c word[i1:] if new_word in word_set: result.append(new_word) return result while left_queue and right_queue: # 每次扩展较小的一侧 if len(left_queue) len(right_queue): left_queue, right_queue right_queue, left_queue left_visited, right_visited right_visited, left_visited for _ in range(len(left_queue)): word left_queue.popleft() for neighbor in get_neighbors(word): if neighbor in right_visited: return step 1 if neighbor not in left_visited: left_visited.add(neighbor) left_queue.append(neighbor) step 1 return 0这里有个关键点双向 BFS 的step计的是从一侧出发已经走的步数当在另一边发现同一个节点时总步数要1。上面的代码在扩展完一层后step 1如果新邻居已经出现在另一侧的 visited 里说明两边刚好相遇步数是step 1。这个边界容易出错建议用一个简单的用例比如hit - hot - dot - dog - cog手动推一遍。4. 实战中容易翻车的四个细节4.1 判重必须放在入队时我见过很多人这样写 BFSnode queue.popleft() if node not in visited: visited.add(node) # 处理邻居出队时才标记 visited会导致同一个节点被多次加入队列。因为在它还没出队之前它的邻居已经可以通过别的路径再次发现它。重复节点入队会造成严重的性能损耗甚至死循环。正确做法是邻居生成之后先判断是否访问过如果没访问过立刻标记 visited 并加入队列。这样每个节点只会在队列里出现一次。不过有一种例外如果需要记录每个节点第一次被访问时的路径或者当前节点的步数你可以把步数打包进队列里比如queue.append((node, step 1))这种情况下标记 visited 的时机仍然是在入队前。4.2 分层计数先圈出当前层BFS 返回步数时最经典的分层写法是while queue: for _ in range(len(queue)): # 处理当前层的一个节点 ... step 1关键点是range(len(queue))必须在处理当前层之前求值。因为len(queue)在循环过程中会变化如果你写的是for _ in range(len(queue))Python 会在进入循环时一次性求值这恰好是对的。如果你写成for _ in range(len(queue)):但循环体内queue长度变化还是会按初始长度遍历所以我们需要的就是这个特性。另一种常见写法是不用for循环而是给每个节点记录步数queue.append((start, 0)) while queue: node, dist queue.popleft() for neighbor in get_neighbors(node): queue.append((neighbor, dist 1))这种写法不需要考虑分层但每个节点都要多存一个整数稍微浪费一点空间。我个人的习惯是如果题目要返回层数用第一种如果只需要遍历所有节点用第二种。两者逻辑不同不要混用。4.3 复杂度与误用场景BFS 的时间复杂度通常可以写成 O(N * K)其中 N 是节点数K 是每个节点的平均邻居数。在网格题里N 是格子总数K 是最多 4 或 8。在状态空间题里N 是状态总数K 是每次转移的数量。空间复杂度最坏情况下是 O(N)因为队列最多可能存储所有节点。如果题目限制空间很小BFS 可能不如 DFS。另外BFS 不是万能的。以下几种情况要慎重边权不全为 1最短步数不等于最短路径长度要用 Dijkstra。图非常大且目标离起点很近BFS 仍然会扩展大量节点可以试试启发式搜索。需要输出所有路径BFS 虽然能找到最短路径长度但要枚举所有最短路径往往需要回溯或记录前驱此时 DFS 更方便。我刷题时吃过一个亏遇到走迷宫输出最短路径的题直接用 BFS 记录前驱结果发现一个格子可能被多个前驱到达如果只记录一个前驱就漏掉了其他路径。正确做法是用数组记录每个节点从哪个方向来最后反向恢复路径。4.4 一个压箱底的双向 BFS 通用写法上面单词接龙里已经展示了双向 BFS这里我把它的通用框架抽出来以后遇到起点和终点都明确的 BFS 题可以直接套from collections import deque def bidirectional_bfs(start, end, neighbors_func): if start end: return 0 left deque([start]) right deque([end]) left_visited {start} right_visited {end} step 0 while left and right: step 1 # 固定从较小的一侧扩展 if len(left) len(right): left, right right, left left_visited, right_visited right_visited, left_visited for _ in range(len(left)): node left.popleft() for next_node in neighbors_func(node): if next_node in right_visited: return step 1 # 两侧在下一层相遇 if next_node not in left_visited: left_visited.add(next_node) left.append(next_node) return -1这个通用版本有两点需要特别注意每次扩展前先交换左右队列保证每次都扩展更小的一侧这样能显著减少总扩展节点数。但交换后left和right的含义会变所以left_visited和right_visited也要跟着交换。如果你觉得交换容易绕晕也可以不交换只用两个队列分别扩展写起来更简单只是效率稍差。step在每次循环开始时加一然后返回step 1是因为当前扩展的这一层还没有计入step而相遇节点所在的层需要额外加上。你可以把step初始化为 0然后在返回时统一加 1。这个细节每个写法都不同一定要用例子验证。根据我个人的刷题经验双向 BFS 在单词接龙这种分支数大的场景能把搜索空间从指数级降到约开根号级。比如单向需要扩展 10^6 个节点双向往往只需要扩展 10^3 * 2。但前提是你能明确给出起点和终点如果目标不明确双向 BFS 根本没法用。最后分享一个我自己的习惯无论遇到多简单的 BFS 题我都会先写一个neighbors函数把状态转移逻辑单独隔离出来。这样即使后面要改成双向 BFS或者加剪枝条件也只改这一个函数。很多同学喜欢把所有逻辑堆在 while 循环里结果代码越长越乱出了 bug 也不容易定位。把怎么找邻居和怎么遍历分开是 BFS 代码保持可维护性的关键。
阅读完成 · 觉得有帮助？
