企业官网建设流程全解析

BFS（Breadth-First Search，广度优先搜索）是很多人的第一个图论算法，也是最容易被低估的一个。我最早接触BFS是在刷“走迷宫”题目的时候，当时觉得这就是一个死板的模板：建队列、出队、扩散、入队，循环到队列空为止，完事。后来做的题目多了才意识到，BFS真正厉害的地方不在于这个循环本身，而在于“队列里的每一层代表着什么”“什么时候可以提前出答案”“状态怎么设计才不会爆内存”这些看起来隐性问题。这篇就从最底层的原理讲到刷题实战中真正会用到的几种变形，把适合BFS处理的场景和需要用DFS或更高级算法的场景一并讲清楚，适合刚接触图搜索的初学者，也适合想系统梳理BFS脉络的进阶者。

1. BFS核心原理——为什么队列能“一层一层”地搜索

1.1 树的层序遍历是BFS的最直观雏形

理解BFS最简单的方式是回到二叉树层序遍历。想象一棵树上有一个根节点，它的左右孩子排在第一层，孩子们的子孙排在第二层，如果用一个队列，先让根节点入队，然后每次从队首取出一个节点，把它的所有子节点塞到队尾，这样做出来的访问顺序一定是：根、所有第一层孩子、所有第二层孙辈、所有第三层…… 这在多层结构里，就是“按层推进”而不是“一条道走到黑”。BFS在图上的行为完全一致，区别只是图上节点可能被多条路径到达，需要额外一个visited记录来防止重复访问。

很多初学者会把BFS理解成“用队列遍历”，这个说法没错但不够本质。BFS的本质是维护了一个边界集合，队列里同时存的是当前这一层的待扩展节点。每从队列头部弹出一次，就是扩展一个节点；每往队列尾部加入一次，就是把下一层的候选节点纳入边界。因为队列是先进先出的，先入队的节点先被扩展，所以同一层的节点一定比下一层的节点先被处理。这个“层的概念”是BFS的关键，也是它比DFS更容易在特定问题上得出最优解的根本原因。

1.2 无权图最短路：为什么“先到达的路径就是最短的”

BFS最经典的应用是求无权图（所有边权重都为1）的最短路径。要明白为什么第一次访问到一个节点，走的距离一定是最短的，可以用数学归纳法来理解：第0层只有起点本身，起点到起点的距离为0，这是最短的；假设第k层的每个节点都被以“最短距离k”首次访问，那么从一个第k层节点扩展出来的第k+1层邻居，从起点到它的路径长度是k+1。如果有另一条更短的路径能到达这个邻居，长度必然小于k+1，这意味着在更早的层就该访问到它，但一层一层地扩散决定了“更早的层”会在“更晚的层”之前被处理完，所以这个更短的路径要么根本不存在，要么已经在这个邻居入队时被访问过了。

我在实际做题时经常给初学者讲一个生活类比：想象你在一个空旷的操场上往水里扔一块石头，水波会从落点一圈一圈向外扩散。第一圈是距离1的位置，第二圈是距离2的位置，每一圈比上一圈半径大1。水波永远不会跳过内圈直接到达外圈。BFS就是这个水波的数字化版本，每一轮循环对应一圈扩散，这个性质让它在“最少步数”“最短距离”这类问题上天然正确。这也是为什么BFS和动态规划经常出现在同一个题目里的原因，很多题目先BFS建图，再DP求值，两套思想配合起来效率很高。

2. BFS的两种主流写法——从模板到手写代码

2.1 标准队列模板的四要素

写BFS之前先记住四个关键点：队列、访问标记、方向/邻居生成、距离数组（或步数记录）。我把这套模板固定在脑子里之后，几乎能应付所有BFS题目。队列可以用Python的deque，不要用list，因为list的pop(0)是O(n)操作，在大数据量下会退化得很厉害。访问标记可以是二维数组、哈希集合，或者直接在原数组上打标记。邻居生成最常见的就是上下左右四个方向，有些题是八个方向，有些题是“改变一个字母得到单词”这种规则，总之核心就是“从当前状态能去哪些状态”。

模板的骨架大致是下面这个模式，我一般习惯在入队时立即标记visited，这样可以避免同一个节点被多个邻居重复入队：

from collections import deque def bfs(start, target, can_pass): # 1. 队列和初始状态 q = deque() q.append(start) visited = set() visited.add(start) step = 0 # 2. 向外扩展 while q: # 3. 处理当前层的所有节点 for _ in range(len(q)): cur = q.popleft() if cur == target: return step # 4. 生成下一层候选 for nxt in get_neighbors(cur): if nxt not in visited and can_pass(nxt): visited.add(nxt) q.append(nxt) step += 1 return -1

2.2 例题实战：模板如何套进“最短路径”题

拿LeetCode 1091矩阵中的最短路径来实际走一遍。这个题给一个n乘n的0/1矩阵，0表示可以走，起点是左上角，终点是右下角，每一步可以向周围8个方向移动。要计算最短路径长度。用上面的模板，start是(0,0)，target是(n-1, n-1)，can_pass是“坐标未越界且矩阵值为0且未访问”。8个方向可以用两个数组生成，或者直接写一个dirs列表：

dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

步骤计数也很直接：初始步数为1（起点本身占据一步），每扩展一层步数加1。我第一次写这个题时犯过一个典型错误，就是在出队时才标记visited，结果在本应去重的场景里出现了大量重复入队，一个100乘100的矩阵跑出了上千万次循环，直接超时。后来改成入队时立刻标记，问题就消失了。这算是BFS实现里的一个经典陷阱，后面我会专门展开讲。

3. BFS和DFS到底怎么选——搜索算法的两条路线

3.1 遍历顺序的差异决定了各自的适用场景

DFS（深度优先搜索）走的是“一条路走到黑，走不动再回头”的路线，递归实现极其简洁，两行代码就是一个朴素DFS。BFS走的是“层层推进”的路线，牺牲一点代码直观性，换来的是天然按距离递增的顺序访问节点。这个差异直接带来了两种算法的分工：如果你关心的是“是否存在一条路径”，DFS通常更省空间，因为递归栈深度等于路径长度，而BFS需要维护整个待扩展层的节点，最坏情况下空间复杂度是指数级的；但如果你关心的是“最短路径多少步”，BFS是优先选择，因为DFS找到的第一条路径不一定最短，要找到最短路径往往需要遍历全部路径做比较，复杂度会高很多。

实际做题时，我会先看题目里的关键词：出现“最少步数”“最短路径”“最少操作次数”这类词，第一反应就是BFS；出现“是否存在”“能不能到达”“所有可能的路径”“回溯枚举”这类词，第一反应是DFS或回溯。比如扫雷游戏展开空白格适合DFS，因为目标是快速找到一个方向上的连续空白；而题目里如果问“从起点到终点的最短路”，DFS大概率不是好选项。

3.2 空间与时间的取舍：一个容易被忽略的维度

很多人对比DFS和BFS只看时间不看空间，实际上空间复杂度往往才是决定一个搜索算法能不能跑通的关键。DFS用系统递归栈，在一条很深的链上可能只需要O(d)的空间，其中d是路径深度；BFS会在队列里同时保存一层的所有节点，如果图的分支因子很大，比如每个节点能扩展出100个邻居，扩展3层之后队列里就会出现上百万个节点，内存直接爆炸。反过来，如果图是矮胖型，即层数少但每层节点极多，DFS就没有明显优势。

我在参加算法竞赛时有一个经验法则：如果确认是无权图并且要求最短路，直接BFS，不用犹豫；如果题目数据范围极大且只需要连通性判断，先用并查集，再用DFS，最后才考虑BFS；如果图是隐式图，即状态空间需要动态生成的图（比如拼图游戏、魔方状态、字符串变换），默认大概率是BFS或双向BFS，因为这类题求的往往是“最少步数”。下面这个表是我在选择时常用的快速对照：

3.3 DFS和BFS的混用：有些题两条路都要走

有一个常被初学者忽略的点：BFS和DFS并不是互斥的，很多高效解法是两种搜索的配合。经典例子是“在迷宫里找最短路径并打印路径”，先用BFS从起点到终点算出距离，再用DFS（或反向BFS）根据距离矩阵回溯出具体路径。前向BFS保证了“距离最短”，反向回溯保证了“沿着可行路径走”，两套思路合起来才能既拿到最优值又拿到具体方案。

还有一种更常见的混用场景是“先用DFS建图，再对图做BFS”。比如在括号生成、表达式求值、连通块问题里，先用DFS枚举所有可能状态或块结构，再把状态之间的关系存入邻接表，最后用BFS求某个状态到目标状态的最少变换次数。我在做“滑动谜题”这类题目时就是这么干的：状态空间较小但变换规则复杂，先用DFS穷举出所有可达状态并建边，再用BFS求最少步数，代码虽然长一点，但每一段的逻辑都变得非常清晰，排错也轻松很多。

4. BFS到A*：从“无脑扩散”到“带指南针的搜索”

4.1 A*多出来的启发式函数到底在干什么

A算法是BFS的一个升级方向，它在BFS的“层序扩散”基础上增加了一个启发式函数h(n)，用来估计从当前节点n到目标节点的剩余代价。A每次从优先队列（按f(n)=g(n)+h(n)排序，g(n)是从起点到n的已知代价）中取出f值最小的节点来扩展，而不是像BFS那样严格按层级来。直观上，A就像一个有了“指南针”的旅人，BFS会向四周均匀撒网，A则会优先朝目标方向收缩搜索范围。

这里有一个关键点需要分清：BFS其实是A在h(n)=0时的特例。当所有边的权重都为1且没有启发式信息时，A退化成按g值排序的Dijkstra，如果所有边的权重都是1，Dijkstra又退化成BFS。所以可以这样理解：BFS是最基础的地毯式搜索，A是有方向性的加速搜索。但A的加速效果完全依赖h(n)的质量，如果h(n)设得不好，比如高估了实际剩余代价，A*甚至会丢掉最优解；如果低估太多，搜索范围又会变大，退化得很接近Dijkstra。

4.2 对比：什么时候A*能碾压BFS，什么时候BFS更稳

真实场景里，BFS和A的取舍直接和问题规模、启发式信息的质量挂钩。一个特别典型的例子是八数码/十五数码问题，BFS要遍历的状态空间极其庞大，15数码的完整状态空间大约是15的阶乘量级，BFS根本不可能在有限时间内跑完；而A配合曼哈顿距离作为启发式，能在很短时间内找到最短解。反过来，如果问题只是一个平面网格上的简单寻路，并且网格尺寸不大，BFS代码简洁、无参数依赖、没有任何调优空间，反而更稳定；A*需要你额外实现优先队列和启发式函数，代码量多出一截，而且很容易因为h(n)设计不当出现性能浮动。

从工程视角看，我更愿意用下面几条经验来判断：

• 状态空间小于10^6，直接用BFS，没必要上A*。
• 状态空间大但能设计出“信息丰富”的启发式（比如曼哈顿距离、欧氏距离、错位数），优先考虑A*。
• 启发式很难设计，或者状态之间的转移代价不是统一的，考虑Dijkstra而不是A*。
• 游戏地图寻路这种场景，A*几乎是标准答案，因为地图大但路径方向性明确。

值得注意的是，A虽然在方向上优于BFS，却不一定在时间上优于BFS，如果数据集规模太小，优先队列的堆操作开销反而会让A更慢。我在实测一些题库数据时，棋盘在8×8以下时BFS往往更快；但棋盘一变大，A的优势立刻显现。所以不要盲目“上A”，先估算状态数量和启发式质量，再做选择。

下面这个表是我在实际选型时常用的快速对照：

5. BFS在二维矩阵和状态搜索里的实战拆解

5.1 多源BFS：腐烂的橘子问题（LeetCode 994）

很多刚入门的人会以为BFS只能从一个起点开始搜索，实际上多源BFS在很多题目里是核心考点。LeetCode 994“腐烂的橘子”就是一个经典例子：二维数组里0代表空、1代表新鲜橘子、2代表腐烂橘子，每分钟腐烂橘子会感染四邻域的新鲜橘子，问多少分钟后所有橘子都腐坏。这个题的关键是所有腐烂橘子在时间0时就同时开始感染，所以需要把所有腐烂橘子一次性全部入队，再统一按层扩散。

实现上很简单，第一遍遍历时把所有值为2的格子全部加入队列，同时统计新鲜橘子数量。然后开始BFS，每过一分钟扩展一层，每感染一个新橘子就把新鲜橘子数量减1。最后如果新鲜橘子数量为0，返回扩展的层数，否则返回-1。我特别想提醒的一点是：这里你可以不用额外的visited数组，直接在原矩阵上把新鲜橘子改成腐烂橘子就行，这样既能节省空间又能避免重复访问，但要注意不要把本轮已经感染的和下一轮才感染的情况混了，因为改完之后它会继续被当作“已腐败”的状态参与判断。

多源BFS的思想还可以扩展到“网格中的最近距离”这类题目，比如LeetCode 542“01矩阵”，求每个0到最近的1的距离。这类题如果对每个0都做一次BFS，复杂度是O(n^2)，数据一大就会超时；正确做法是把所有1入队，做一次多源BFS，一次跑出所有0到最近1的距离。训练多源BFS有助于建立“反向思维”：问题里的多个起始点，往往可以合并成一个“虚拟起点”。

5.2 状态空间搜索：单词接龙（LeetCode 127）

BFS不仅能用在矩阵格子上，还能用在“状态”上。LeetCode 127“单词接龙”是BFS在隐式图上最经典的题目之一：给定开始单词、结束单词和一个单词字典，每次只能改变一个字母，问从开始单词到结束单词的最短变换序列长度。这里每个单词是一个节点，两个单词之间如果只差一个字母就在图中连边。图本身没有显式给你，需要BFS在每次扩展时现场生成邻居。

写这类题时有一个性能优化点：不要每次枚举字典里的所有单词来判断是否只差一个字母，那样复杂度是O(N×L)（N是字典大小，L是单词长度），数据一大就超时。标准做法是穷举当前单词每一位的26种替换，然后在字典集合里查询，这样每个状态的扩展量是26×L而不是N。我第一次做这题时直接用了双重循环枚举字典，在5000个词的用例上跑了接近两秒，改成字母替换后瞬间降到几十毫秒。这道题可以看作是BFS在“非网格图”上的标准模板，掌握了它，很多字符串变换、状态转移类的BFS题都能直接套。

另一个可以补充的思路是双向BFS：从开始单词和结束单词同时向中间搜索，每次扩展节点数较少的那一端，当两端的访问集合出现交集时，就找到了最短路径。双向BFS在状态空间很大的时候效果非常明显，可以把搜索深度变为原来的一半，状态数量则是平方根级别的缩减。单词接龙这个题的官方数据范围其实不大，很多情况单向BFS也能过，但一旦你的起点和终点相距很远，双向BFS几乎是必须的优化手段。

5.3 拓扑排序视角的BFS：课程表（LeetCode 207）

拓扑排序很多人是在学图论时接触的，但真正实现的时候会发现它本质上就是一个BFS变体。LeetCode 207“课程表”判断课程之间的先修关系是否存在循环，也就是判断有向图是否无环。标准解法是Kahn算法：先统计每个节点的入度，把所有入度为0的节点放入队列，然后反复出队，每出队一个节点就把它所有邻居的入度减1，减到0就把邻居入队。如果最后出队的节点数量等于总节点数，说明图无环，否则说明存在环。

这个算法没有显式地按“层”推进，但它用队列处理节点的顺序完全符合BFS的思想。我遇到不少初学者会把拓扑排序和DFS强绑定，认为只有DFS才能做判环，实际上Kahn算法配合队列实现起来更直观、更好写。用这个算法还可以顺手求出拓扑序列，很多题目会在判环基础上进一步要求输出一种合理的课程安排顺序，这时候只需要把出队顺序记录下来就是一组拓扑序。

5.4 双向BFS：搜索空间爆炸的对策

上面单词接龙已经提到了双向BFS，这里单独拿出来再拎一下。单向BFS的问题是每扩展一层，队列里的节点数可能指数增长，很多状态都在“无用”地扩散。双向BFS的思路是让起点和终点各自向外扩散，每次扩展节点数更少的一端，直到两个方向的搜索前沿相遇。在无向图中，双向BFS缩减的搜索空间尤其明显：如果目标在第d层，单向BFS要访问约b^d个节点，双向BFS每边只需访问约b^(d/2)个节点，总访问量从指数降为平方根级别。

实现双向BFS时有几个容易踩的坑：两个方向最好都维护独立的visited集合和距离字典；每次扩展完当前层后要检查两个集合是否有交集；如果某一方向的队列已经空了，说明搜索无法继续，可以直接返回无解。我在做“打开转盘锁”（LeetCode 752）时，用双向BFS比单向BFS快了接近5倍，从1200ms降到240ms左右。

6. BFS中的常见问题与排查技巧实录

6.1 边界条件与访问标记的位置

写BFS最常见的错误有两个，一个是忘了处理边界条件，一个是visited标记位置放错。边界条件包括坐标越界、矩阵值不合法、字典里不存在、重复状态等，很多人喜欢在生成邻居时才判断边界，这没问题，但一定要保证判断条件覆盖完整。比如在矩阵里，至少要确保行号和列号同时满足0 <= r < m和0 <= c < n，少一个条件就可能导致程序越界或者误访问。

visited标记位置的问题我在前面已经提过，这里再展开一下：如果你在出队时才标记visited，同一层里的两个不同节点可能同时生成同一个邻居，导致这个邻居被重复加入队列两次。虽然最终结果可能依然正确（因为重复访问只是浪费），但会造成大量额外开销。正确做法是当节点被加入队列的那一刻就标记为已访问，这样可以保证队列中永远不会出现重复状态。还有一种特殊情况是，如果你在多层循环里修改了原数组作为visited，一定不要在回溯时把它改回来，否则会重复入队，导致死循环。

6.2 内存爆炸：层数多节点多怎么办

BFS空间爆炸是小状态空间题目里不太容易遇到的，但一旦出现，往往没办法靠简单的参数调整解决。遇到这类问题时，我会按优先级尝试以下措施：先检查是否真的需要把每个状态都压入队列，有些状态可以提前剪枝；再考虑用双向BFS来平衡空间消耗；如果状态是整数或可以用位运算压缩的，尽量用int或位掩码存储状态，而不是用字符串；如果内存依然吃紧，可以尝试用DFS加迭代加深（IDDFS），用时间换空间。

举个简单的例子，如果状态是一个3×3的棋盘，用字符串存是9个字符，但用整数存可能只需要一个int，内存差距接近10倍。编译型语言里还可以用数组代替哈希集合做visited，Python里可以用bytearray来代替set以节省大量内存。这些都是实战里很实用的优化手段。

6.3 方向数组与邻接表：两种图模型下的初始化习惯

在矩阵类型的BFS里，方向数组的写法直接影响代码的可读性与出错概率。我习惯写成二维列表，比如dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]，这样在循环里直接for dr, dc in dirs:就能拿到四个方向的偏移量。如果把方向写成一维的重复判断，代码会瞬间又臭又长，而且少一个方向都不容易一眼看出来。

在非矩阵的图模型下，邻接表的构建是另一个容易出问题的地方。图论题里BFS之前通常要先建图，如果题目给的是稀疏图，邻接表可以节省大量空间；如果给的是稠密图，邻接矩阵反而更快。我在做BFS题时有一个习惯：先把问题的图模型确定清楚，明确节点是什么、边是什么、是否有向、是否有环，然后再写代码。不要一上来直接写循环，否则很容易把隐式图的方向搞错。

6.4 升级路线：01-BFS与其他变形

最后补充一个BFS的进阶变体：01-BFS，适用于边权只有0和1的最短路问题。它的做法是用deque替代普通队列：如果移动代价为0，就把新节点加入队首；如果移动代价为1，就加入队尾。这样仍然能保持单调性，并且比Dijkstra更快，因为不需要优先队列维护堆结构。这个技巧在处理带障碍物的网格寻路、电梯调度问题时非常有用，比如LeetCode 1368“使网格图至少有一条有效路径的最小代价”就是一个典型例子。

从BFS到双端队列BFS，再到A*，这个知识链条能覆盖绝大部分搜索题。我个人的体会是，不要一开始就追求复杂的算法框架，BFS和它的一系列变形已经是极强的基础工具，先把队列操作、访问标记、层数统计这三件事吃透，再去接触更复杂的变体和优化，才不会在写代码时手忙脚乱。最后再分享一个小习惯：每写完一个BFS，我都习惯性地在脑子里跑一遍数据量最小的用例，再跑一遍边界用例，比如起点就是终点、图里根本没有路径、矩阵只有一行等，这比写完直接提交、被用例卡住了再回头改要高效得多。