我早年刷题的时候对BFS广度优先搜索一直有种“看过就忘”的错觉。因为DFS递归写起来太顺手了三五行搞定一个树遍历而BFS总得多写一个队列还得惦记着“什么时候入队、什么时候出队、要不要标记已访问”。直到后来做迷宫最短路径、网络拓扑分层、社交关系扩散这类实际问题我才真正意识到BFS不是“另一种遍历方式”它是对“层级扩散”和“最短路径”这两个直觉的精确建模。这篇博文我就把BFS掰开揉碎讲一遍从算法思想、代码模板、应用场景到和DFS的对比最后再聊几个进阶玩法争取让新手看完能直接上手让老手也能在细节上有点收获。BFS到底是什么一句话从起点出发一层一层往外扩散先访问距离起点为1的所有节点再访问距离为2的所有节点依此类推。这里的“距离”指的是边数或步数。正是这种“逐层推进”的特性让BFS在无权图中天然具备“最短路径”语义——第一次访问到目标节点时走的路径就是最短路径。这个性质是BFS区别于DFS最核心的价值也是很多面试题的考点。1. BFS到底在做什么——提起BFS先想这棵“扩散树”1.1 一张图看懂BFS的遍历顺序想象你在一个迷宫里站在起点手里有一串钥匙每把钥匙能打开一扇门。你先把与你直线相邻的所有房间门打开记录下这些房间然后依次站在这些房间里再打开它们相邻的、还没打开过的门。这个过程就是BFS你永远优先处理“当前这层”的房间而不是一头扎进某个走廊深处。如果把访问顺序画出来BFS访问到的节点会形成一棵“扩散树”根节点是起点第一层是所有直接邻居第二层是邻居的未访问邻居以此类推。有一个很容易被忽略的细节是BFS的扩散树不一定覆盖整个图的所有边它只保留“每个节点第一次被访问时”的那条边。也就是说同一个图从同一个起点出发BFS生成的扩散树是唯一的前提是邻居的遍历顺序固定但DFS的递归树可能会因为不同的回溯顺序产生不同的形状。这一点在理解“BFS为什么能找到最短路径”时特别关键。1.2 BFS为什么能找到最短路径——层级记录的数学基础要理解BFS的最短路径性质关键在于“访问距离”的单调性。BFS按层访问当一个节点被第一次访问时它所在的层数恰好等于它到起点的最短距离。这个结论可以用归纳法证明第0层只有起点本身距离为0假设前k层的所有节点的访问距离正确那么第k1层的节点必然是通过某个第k层节点扩展来的它的最短距离不可能小于k1否则应该更早被访问也不可能大于k1因为第k层邻居到它只需一步。因此访问距离就是最短距离。这个性质在实际代码里的体现就是很多BFS实现中会用dist数组记录“到达每个节点时已经走过的步数”或者用队列中每个元素携带的“层数/步数”字段。如果你不记录层数BFS依然能保证“第一次碰到目标节点时路径最短”但你在回溯路径时需要额外维护一个“前驱节点数组”否则只能确认最短距离是多少拿不出完整路径。这个坑我见过不少新手踩过后面代码部分会专门讲。2. 从零手写BFS——代码模板逐行拆解2.1 选对数据结构为什么是queue不是stackBFS的核心数据结构是队列Queue先进先出FIFO。为什么队列能体现“逐层扩散”因为先入队的节点先被处理而它扩展出的下一层节点会排在这一层的所有节点后面。你可以把队列想象成“待办清单”先来的任务先做做任务的过程中发现的新任务追加到队尾这样一来同层级的任务自然会被连续处理完。如果换成栈LIFO那就变成DFS了——最新发现的任务优先处理你会一路扎到最深处才回头。在Python里我建议用collections.deque而不是list来实现队列原因是list的pop(0)操作是O(n)的它会移动整个列表的元素deque的popleft()是O(1)的。这个差异在大规模图遍历时是明显的哪怕是一个几万节点的图用list做队列都会感觉到卡顿。如果你用C直接#include queue用std::queue即可。2.2 完整代码模板Python C这是我在LeetCode和实际工程中反复使用的一套BFS模板注释里标了每一步的作用from collections import deque def bfs(start, graph): param start: 起点可以是节点编号、坐标元组等 param graph: 邻接表/邻接矩阵/网格等可遍历结构 return: 从start出发的遍历顺序或所需的最短距离 # 1. 初始化队列和访问标记 queue deque([start]) visited {start} # 用set标记已访问防止重复入队 # 如果只需要最短距离可以再加一个dist字典/数组 # dist {start: 0} while queue: # 2. 取出队首节点 node queue.popleft() # 处理当前节点比如打印、收集结果 # print(node) # 3. 扩展所有未访问的邻居 for neighbor in get_neighbors(node, graph): if neighbor not in visited: visited.add(neighbor) # 入队前就标记防止重复入队 queue.append(neighbor) # dist[neighbor] dist[node] 1 # return dist, visited对应的C版本#include queue #include unordered_set using namespace std; void bfs(int start, vectorvectorint graph) { queueint q; unordered_setint visited; q.push(start); visited.insert(start); while (!q.empty()) { int node q.front(); q.pop(); // 处理当前节点 for (int neighbor : graph[node]) { if (visited.find(neighbor) visited.end()) { visited.insert(neighbor); q.push(neighbor); } } } }其中get_neighbors函数要根据具体场景实现如果是二叉树就是node.left和node.right如果是网格就是上下左右四个方向如果是邻接表就是遍历graph[node]这个列表。我在实际写题时通常把get_neighbors单独抽出来做参数这样模板可以在不同场景间复用。2.3 模板里最容易写错的三个细节第一个细节是在“入队前”标记visited而不是“出队时”。如果你在节点出队时才标记已访问同一层里多个邻居可能把同一个节点重复入队造成队列膨胀严重时甚至死循环。我之前在写网格类BFS时遇到过重复入队导致内存暴涨的教训就是因为在for neighbor循环里先append再标记。正确做法是一旦决定把邻居入队就立刻把它加入visited。第二个细节是层数的记录方式。有两种常见写法一种是在队列里存(node, depth)元组出队时取出深度另一种是单独维护dist数组每次扩展时dist[neighbor] dist[node] 1。前者写起来简单但每个节点多存了一个数字内存开销略大后者更省内存也方便后续回溯路径。刷题时我倾向于用dist数组因为经常需要同时回答“最短距离”和“最短路径”两个问题。第三个细节是网格类BFS的方向数组。上下左右四个方向的偏移量建议写成directions [(-1,0),(1,0),(0,-1),(0,1)]遍历时逐个加上去同时注意边界判断。我曾经在写“旋转坐标”时把方向数组顺序写错导致BFS只搜索了三个方向最后结果怎么都不对。这种错误在逻辑上很难一眼看出来所以把方向数组和边界检查封装成一个is_valid函数会比到处内联判断更可控。3. BFS的看家本领——四大经典场景逐一把玩3.1 场景一网格/迷宫最短路径这是BFS最经典的舞台。给定一个m x n的网格其中0表示可通行1表示障碍物从左上角到右下角的最小步数是多少思路非常直接把网格的每个格子当成图中的一个节点相邻的可通行格子之间有一条边所有边的权重都是1从起点开始BFS第一次触达终点时的步数就是最小步数。这里有一个隐含条件网格本身是隐式图不需要提前构建邻接表直接在坐标上做扩展即可。我分享一段可以“抄作业”的实现def min_steps_in_grid(grid): m, n len(grid), len(grid[0]) if grid[0][0] 1 or grid[m-1][n-1] 1: return -1 directions [(-1,0),(1,0),(0,-1),(0,1)] queue deque([(0, 0, 1)]) # (row, col, steps) visited {(0, 0)} while queue: r, c, steps queue.popleft() if (r, c) (m-1, n-1): return steps for dr, dc in directions: nr, nc rdr, cdc if 0 nr m and 0 nc n and grid[nr][nc] 0 and (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, steps1)) return -1注意这里我在队列元素里直接存了steps因为题目只要求步数不要求路径这样写最直观。如果要求输出路径那就要维护一个prev字典记录每个格子是从哪个格子走来的最后从终点回溯到起点路径就是逆序的。3.2 场景二二叉树的层序遍历BFS在二叉树里有个特别优雅的应用层序遍历。输出一棵树的每一层节点值本质上就是BFS的天然产物。普通的BFS只需要一个队列就能完成层序输出但如果要求“按层分组”就需要在每一轮循环开始时记录当前队列的长度level_size然后只处理这level_size个节点它们的“下一层节点”会追加到队尾下一轮循环自然就进入下一层。def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result这里的关键是level_size必须在循环开始前固定下来因为循环过程中queue的长度会变化。如果你在循环里动态读取len(queue)就会把下一层的节点也混进当前层。这个技巧在很多“Z字型遍历”“右视图”之类的问题里都是基础操作。3.3 场景三连通块与图的遍历在无向图中从一个起点出发BFS能访问到的所有节点构成一个连通分量。对于非连通图你需要遍历所有节点对每个未访问的节点做一次BFS每做一次的起点就代表一个独立的连通分量。这个思路在“岛屿数量”“省份数量”这类问题里极其常用。以“岛屿数量”为例遍历网格一旦发现一个为1的格子就把它当作岛屿的一部分用BFS把这个格子所在的整座岛屿全部标记为已访问比如改成0岛屿数量加一。BFS在这里做的事情本质上是“确定连通块边界”你并不关心岛屿内部的具体形状只关心哪些格子连在一起。3.4 场景四多源BFS——多个起点一起“进攻”多源BFS是一个容易被新手忽略的进阶写法。普通的BFS只有一个起点多源BFS则在一开始把所有“源点”同时放入队列然后进行扩散让它们像多个声源一样向周围传播。典型例题是“感染传播”或“0-1矩阵距离”给一个矩阵有些格子是0有些是1求每个1到最近的0的距离。做法是把所有0的格子入队距离设为0然后用BFS一层层向外扩散每次扩展时距离加一。因为多个源点在同一条“起跑线”上每个格子第一次被访问时拿到的距离就是它到最近0的距离。这个“多个起点同时开始”的写法让代码不需要对每个0单独跑一遍BFS时间复杂度从O(kmn)降为O(mn)是典型的空间换时间思路。4. BFS和DFS到底差在哪里——一张表格看清全貌4.1 遍历顺序与数据结构的差异BFS和DFS的差异归根结底是“队列vs栈”的差异。BFS按层级访问先处理离起点近的节点DFS按分支访问沿着一条路径走到底再回头。举一个生活化的例子你在一个小区里找某个人BFS的做法是先问所有邻居再问邻居的邻居DFS的做法是走进一栋楼从上到下翻遍每一户翻完再换下一栋楼。数据结构上BFS用队列DFS用栈递归本质上就是函数调用栈。这意味着DFS的实现通常更短——递归天然就是栈行为你只需要处理好“当下这一步”即可BFS则需要显式管理队列代码形式上更“工程化”。从空间占用看BFS在最坏情况下可能需要存储一整层的节点空间复杂度是O(树宽)DFS只需要存储一条路径上的节点空间复杂度是O(树高)。在“深而窄”的图里DFS更省内存在“浅而宽”的图里BFS可能爆内存。4.2 复杂度时间都是O(VE)吗如果你从“每个节点入队/入栈一次每条边被检查至多一次”的角度看BFS和DFS的时间复杂度都是O(VE)。但这里有两个实操中的区别值得注意。一是隐式图的场景比如网格边的数量很难像邻接表那样数清楚但总体遵循“每个格子检查若干方向”的规律时间复杂度接近O(方格数量×方向数)。二是状态空间特别大的场景比如求解数独、华容道这类棋盘类问题V和E会膨胀得很快这时BFS和DFS的复杂度差距会体现在“搜到的空间范围”上而不只是常数级别。有个实用的判断标准如果你关心“最少步数”“最短路径”“按层数由近到远”优先BFS如果你关心“是否存在一条路径”“打印所有路径”“判断连通性”DFS和BFS都行DFS写起来更快。如果状态数量巨大且你知道答案在某一侧很深的地方DFS剪枝可能比BFS更现实。4.3 面试官最爱问“迷宫最短路径”为什么不用DFS很多初学者会问DFS也能遍历迷宫啊为什么最短路径要用BFS关键在于DFS第一次找到终点时走的路径不一定最短。DFS的本质是“沿着一条路走到底”它碰到的第一条可行路径完全取决于邻居的遍历顺序——你恰好先走了那条绕远的路它就先把那条路走完了。虽然你可以让DFS记录所有路径然后取最小值但那样它会探索大量不可能是最短路径的分支效率极低。BFS的特殊之处在于它按距离由近到远访问节点第一次碰到终点时终点所在的层数就是最短距离。因此不需要额外比较或剪枝直接返回即可。这就是“BFS天然适合最短路径”的根本原因。还有一个小延伸如果边有权重普通BFS就失效了因为“按步数分层”不再等价于“按权重分层”这时需要换成Dijkstra算法本质上可以看作带优先队列的BFS扩展。5. BFS进阶——从入门到实战的四个升级点5.1 双向BFS让搜索空间直接开根号双向BFS是面试中偶尔出现的优化技巧适合“起点和终点都明确”的最短路径问题。做法是从起点和终点同时开始BFS让两个“波浪”相向扩散当两个波浪第一次相遇时步数就是两者各自走过的层数之和。为什么双向BFS更快考虑一棵非常大的“搜索树”传统BFS从起点扩散k层可能需要访问b^k量级的节点b是分支因子双向BFS只需要两个方向各扩散k/2层两边合计访问约2×b^(k/2)当k足够大时差距是指数级的。我曾在“单词接龙”这道题上做过实测单向BFS需要几千次节点的扩展双向BFS只需要几百次差距非常明显。但要注意实现复杂度也随之上升——你需要维护两个visited集合和一个总队列或两个队列判断相遇条件时要同时检查两个方向的访问标记。写反方向扩展时代码里容易把“从终点扩展”写成“从起点扩展的镜像”建议先用最简单的单词接龙题练手再碰更复杂的场景。5.2 状态压缩BFS当“步数”不止是坐标时有些BFS的“节点”并不是简单坐标而是一个完整的状态。比如滑动拼图、八数码、推箱子每一步会改变整个棋盘布局你没法用几个整数坐标表示当前状态。此时的技巧是用“状态压缩”把整个状态编码成一个整数或字符串再用哈希表Python里的set/dict来标记访问。以八数码问题为例一个3×3的棋盘有9个位置用字符串“123456780”表示当前布局0代表空格每步移动空格与相邻数字交换产生新的字符串状态。BFS从初始字符串出发目标是“123456780”每一步相当于一次状态转移。因为状态总数是9! 362880完全可以用BFS在可接受时间内求出最少步数。如果你在刷“滑动谜题”这类Hard题状态压缩BFS就是标准解法。这里有一个建议状态表示字符串时入队前先查重否则同一个布局可能反复出现。用一个dict同时记录(字符串-步数)比分开用set和dist更简洁碰到目标状态时直接返回字典里的值。5.3 用“层数”还是“步数”——dist数组与visited数组的分工初学者容易把dist和visited混为一谈。visited只回答“这个节点是否被访问过”dist回答“从起点到这个节点的步数是多少”。在很多问题里visited是dist的派生信息——如果dist[node]有值就说明访问过。但两者是不同的问题visited用于防死循环dist用于输出结果。在只求连通性、不需要距离的场景比如“判断图中两个点是否连通”只用visited就够了在求最短步数的场景两者都需要。还有一个容易踩的坑dist的初始值应该设置成“不可能出现的值”比如-1或inf而不是0。如果你把初始值设为0那起点本身是0它的邻居扩展后也被设为011看起来没问题但如果某个节点从一开始就不可达它的dist也是0输出结果时你就分不清“距离为0”和“不可达”的区别。用-1作为初始值是最稳妥的做法。5.4 实战常见问题速查表我根据自己的刷题和实战经验整理了一份BFS常见问题和解法速查表供参考问题类型典型题目/场景BFS解法要点网格最短路径迷宫寻路、腐烂的橘子方向数组 visited dist/步数字段二叉树层序层序遍历、右视图、Z字型每层固定level_size按层分组连通分量岛屿数量、省份数量遍历所有节点逐个起点触发BFS多源扩散0-1矩阵距离、感染传播所有源点入队步数都从0开始状态转移八数码、滑动谜题、单词接龙状态压缩为字符串/整数哈希表查重拓扑/分层课程表、消息扩散层数BFS天然输出层级结合入度做拓扑排序这里面有两道题我认为是BFS从入门到进阶的分水岭一道是“单词接龙”涉及双向BFS和状态转移另一道是“滑动谜题”涉及状态压缩和哈希查重。把这两题彻底吃透BFS相关的大多数面试题都不再是难题。6. 最后说点实操体会如果你正在准备算法面试我的建议是不要只背模板而是每次写完BFS都问自己三个问题队列里存的是什么visited在什么时候标记dist/step在什么时候更新这三个问题想清楚了BFS的代码怎么写都不会跑偏。我自己刷题时有个习惯——先用文字描述一遍“从起点出发一层层扩散直到某个条件满足”再用代码翻译这个描述比直接背模板要有效得多。另外实际工程中BFS的出现频率可能比想象中高。比如社交网络里“我关注的人里有多少人转发过这篇帖子”就是多源BFS比如地图服务里“离我最近的几家便利店”本质上是多个终点的BFS再比如分布式系统里“消息从一台机器广播到所有机器的层级”也是BFS的分层思想。也许你平时不会显式写while queue:但只要你在处理“层级扩散”“最近可达性”“按距离排序”这类问题时心里能想起BFS这杆尺子这篇博客就没有白写。