1. 从单点到全局BFS算法的核心思想与演进如果你刷过一些算法题或者接触过图论、搜索相关的知识BFS广度优先搜索这个名字你一定不陌生。它就像一位训练有素的侦察兵从起点出发以“一圈一圈”向外探索的方式确保找到的路径是最短的。经典的BFS模型比如走迷宫找最短路径我们通常只设置一个起点然后逐层扩散。这个模型直观、强大是很多算法初学者的必修课。但真实世界的问题往往更复杂。想象一下森林里多处同时起火消防队需要知道火势蔓延到每个位置的最短时间或者在一个社交网络中多个核心用户同时发布消息计算信息到达每个用户的最短路径。这些问题不再是“从一个点出发”而是“从多个点同时出发”。这就是多源BFS要解决的问题。它不再是单个侦察兵而是一支同时从多个基地出发的侦察小队协同绘制整个区域的地图。更进一步在有些场景下每一步的“代价”并不相同。在经典的网格BFS中向上下左右四个方向移动一格代价都是1。但如果我告诉你有些方向移动代价是0比如平地滑行有些方向移动代价是1比如正常行走甚至有些是2比如攀爬我们如何找到总代价最小的路径这就需要引入双端队列广搜也叫0-1 BFS。它像是给侦察兵配备了不同的交通工具在代价不同的道路上采用更聪明的策略进行探索。而最小步数模型则是这类问题最经典的抽象和表述。它不关心你是走迷宫、推箱子还是滑动拼图它只关心从一个初始状态通过一系列允许的操作每一步可能代价相同也可能不同变换到目标状态最少需要多少步。BFS及其变种正是解决这类问题的利器。理解从单源BFS到多源BFS再到双端队列BFS的演进不仅仅是多学几个算法模板更是对“状态搜索”这一核心思想的深化。它能让你在面对各种“最短步数”、“最小代价”问题时迅速识别模型选择最合适的工具写出高效而优雅的代码。接下来我们就层层拆解看看这些“侦察兵”是如何升级装备、改变战术的。2. 温故知新经典单源BFS的核心框架与“最短”的保证在深入高级变种之前我们必须牢牢夯实单源BFS的基础。它的核心思想可以用一句话概括由近及远层层扩展。算法使用一个队列Queue来维护待访问的节点遵循“先进先出”的原则这天然保证了距离起点近的节点会优先被访问。我们以一个经典的二维网格迷宫为例。假设在一个n x m的网格中‘.’代表可通行的空地‘#’代表障碍物我们从起点(sx, sy)出发希望找到到达终点(tx, ty)的最短步数。每次可以向上下左右四个方向移动一格。2.1 标准代码框架与逐行解析下面是一个极具代表性的C实现框架几乎可以套用于所有网格类单源最短路径问题#include iostream #include queue #include cstring using namespace std; typedef pairint, int PII; // 用pair存储坐标(x, y) const int N 1010; // 根据问题规模定义 int n, m; char g[N][N]; // 存储网格地图 int dist[N][N]; // 存储从起点到每个点的最短距离同时兼作visited数组 // 四个方向向量上、右、下、左 int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; int bfs(int sx, int sy, int tx, int ty) { // 初始化距离数组为-1表示未访问 memset(dist, -1, sizeof dist); queuePII q; // 起点入队并标记 q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { auto t q.front(); q.pop(); // 如果到达终点直接返回距离。由于BFS特性第一次到达就是最短距离。 if (t.first tx t.second ty) { return dist[tx][ty]; } // 遍历四个方向 for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; // 核心判断逻辑1.不越界 2.不是障碍 3.未被访问过 if (x 0 x n y 0 y m g[x][y] ! # dist[x][y] -1) { // 新点的距离等于当前点距离1 dist[x][y] dist[t.first][t.second] 1; q.push({x, y}); } } } // 队列为空仍未找到终点说明终点不可达 return -1; }为什么这个框架能保证找到最短路径关键在于队列的“先进先出”和距离数组dist的更新方式。起点距离为0入队。然后所有距离起点为1的节点会在第一轮循环中被发现并入队它们的dist被设为1。接着当处理这些距离为1的节点时会发现所有距离为2的节点且未被访问过的……如此往复。因为队列保证了距离为d的所有节点一定在距离为d1的节点之前被处理所以当第一次搜索到终点时其dist值必然是最小的。2.2 关键细节与避坑指南状态判重是生命线dist数组在这里扮演了双重角色记录最短距离和标记是否已访问。dist[x][y] ! -1就意味着这个点已经被更早或同等距离访问过。忘记判重是BFS导致死循环或结果错误的最常见原因。想象一下如果不判重A点走到B点B点又走回A点算法就会在这两点间无限循环。在出队时判断终点 vs 在入队时判断终点上面的代码是在从队列中取出节点q.front()时判断是否为终点。这没有问题因为BFS保证第一次取到终点时距离最短。你也可以在将新节点入队前判断逻辑上是等价的。但绝对不能在刚计算出新坐标(x, y)时就立刻返回因为此时还没有为这个点计算dist值或者计算可能不完整。距离数组的初始化memset(dist, -1, sizeof dist)将距离初始化为-1这是一个非常实用的技巧。-1明确表示“未访问”而任何非负整数都表示一个有效距离。这比单独使用一个bool visited数组更简洁。方向向量的运用使用dx[4]和dy[4]数组来定义方向比写四个独立的if语句更优雅也更不容易出错。当需要处理八方向包括对角线时这个技巧的优势更加明显。实操心得在竞赛或面试中我习惯将BFS封装成一个返回int最短步数或vector路径的函数。dist数组一定要开成全局变量或在堆上分配避免在函数内开大数组导致栈溢出。对于n, m在几百以上的网格局部数组非常危险。3. 化繁为简多源BFS的建模思路与高效实现现在我们来升级问题。不再是单一火源而是多处同时起火。我们想知道火蔓延到每个空地的最短时间。最笨的办法是对每个火源都跑一遍单源BFS然后对每个空地取所有BFS结果的最小值。时间复杂度是O(k * n * m)k是火源数量这显然不够高效。多源BFS提供了一个O(n * m)的优美解法。其核心思想是在初始化队列时将所有“源点”一次性全部加入队列并设置好它们的初始距离通常为0。然后就像普通的BFS一样进行扩展。3.1 算法步骤拆解初始化创建一个距离数组dist初始化为-1表示未到达。创建一个队列q。多源入队遍历整个网格将所有火源点或多个起点的坐标加入队列并将这些点在dist中的值设为0。标准BFS扩展开始标准的BFS循环。每次从队头取出一个点检查其四个邻居。如果邻居是空地且未被访问过dist为-1则将其dist更新为当前点dist 1并将其入队。结果当BFS结束后dist数组中就存储了每个空地距离最近火源的最短蔓延时间。对于障碍物或火源点本身可以根据需要特殊处理。3.2 为什么这样是对的我们可以把多个源点想象成在“第0层”同时存在。BFS的第一轮扩展会找出所有距离任意一个源点距离为1的点。这些点会被标记距离1并入队。接下来从这些距离为1的点扩展会得到所有距离为2的点……这个过程和单源BFS完全一致只不过初始的“波前”不再是一个点而是一个点集。由于BFS的层次扩展特性每个点第一次被访问时一定是被离它最近的那个源点访问到的因此记录的距离就是最短距离。3.3 代码实现对比我们修改之前的bfs函数使其适应多源。假设火源点在地图中用‘F’表示。// dist数组存储每个点到最近火源的距离 void multiSourceBfs() { memset(dist, -1, sizeof dist); queuePII q; // 步骤1: 找到所有源点并加入队列 for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] F) { // 找到火源 q.push({i, j}); dist[i][j] 0; // 火源本身距离为0 } } } // 步骤2: 标准BFS过程 while (!q.empty()) { auto t q.front(); q.pop(); for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; if (x 0 x n y 0 y m g[x][y] . dist[x][y] -1) { dist[x][y] dist[t.first][t.second] 1; q.push({x, y}); } } } }执行完这个函数后对于任意一个空地(i, j)dist[i][j]就代表了火蔓延到该处所需的最短时间。如果dist[i][j] -1说明该点被障碍物包围火永远无法蔓延到。3.4 典型应用场景与扩展森林大火蔓延模拟如上所述。多个起点的最短路径问题例如在一个地图上有多个快递站求每个居民楼到最近快递站的距离。岛屿问题变种求所有海洋格子到最近陆地的距离LeetCode 1162. 地图分析。“广播”问题多个消息源同时广播求消息到达每个节点的最短时间。注意事项多源BFS的“源点”在初始时是平权的即它们的初始距离相同通常为0。如果源点具有不同的初始“强度”或“起始距离”需要在入队时赋予不同的dist初始值。这时队列中初始就包含了不同层次的点但BFS的过程依然能保证正确性因为队列保证了距离小的点优先被处理前提是所有边的权重非负且相等这里是1。如果边权不同则需要用到优先队列BFS的进一步升级——Dijkstra算法这超出了本文基础BFS的范畴。4. 代价分化双端队列广搜0-1 BFS的原理与降维打击现在让我们进入BFS的另一个进阶形态双端队列广搜Deque BFS它特别擅长解决边权只有两种值通常是0和1的最短路径问题。考虑这样一个问题在一个网格中你可以向上下左右四个方向移动。但是向上和向下移动不消耗步数代价为0向左和向右移动消耗1步代价为1。求从起点到终点的最小代价。如果用普通BFS我们无法处理代价为0的边。因为BFS的队列认为每一层扩展代价都是1。如果用Dijkstra算法可以解决但杀鸡用牛刀时间复杂度是O(E log V)。0-1 BFS提供了一个O(V E)的线性解法。其核心在于使用一个双端队列Deque来代替普通队列并修改入队策略如果通过一条代价为0的边到达一个新节点就将这个新节点从队头插入。如果通过一条代价为1的边到达一个新节点就将这个新节点从队尾插入。4.1 算法正确性直观理解你可以把双端队列想象成一个“两端都能进出的管道”。从队头取出的元素我们认为是当前“代价最小”的待处理节点。初始时起点代价0在队头。当我们通过代价0的边扩展时新节点的代价和当前节点相同。为了让它们能尽快被处理我们将其压入队头。这样下一轮循环就会优先处理这些代价不变的节点保持了“优先扩展代价小节点”的顺序。当我们通过代价1的边扩展时新节点的代价比当前节点大1。我们将其压入队尾就像普通BFS一样。这个过程本质上是在模拟一个“简化版的Dijkstra算法”。由于边权只有0和1我们不需要复杂的优先队列堆只需要一个双端队列就能维持节点的“优先级”顺序。4.2 代码框架示例假设grid[x][y]存储了该点的类型0代表代价为0的移动可达1代表代价为1的移动可达。我们用一个deque来维护队列。#include deque // ... 其他头文件和定义 int zeroOneBfs(int sx, int sy, int tx, int ty) { memset(dist, -1, sizeof dist); dequePII dq; // 使用双端队列 dq.push_front({sx, sy}); // 起点从队头入队 dist[sx][sy] 0; while (!dq.empty()) { auto t dq.front(); dq.pop_front(); // 找到终点即可返回因为队头保证当前最小代价 if (t.first tx t.second ty) { return dist[tx][ty]; } // 假设有四个方向代价存储在cost[4]数组中值为0或1 int cost[4] {0, 1, 0, 1}; // 示例上(0), 右(1), 下(0), 左(1) for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; int w cost[i]; // 本次移动的代价 if (x 0 x n y 0 y m grid[x][y]是可通行的 dist[x][y] -1) { dist[x][y] dist[t.first][t.second] w; if (w 0) { // 代价为0插入队头 dq.push_front({x, y}); } else { // w 1 // 代价为1插入队尾 dq.push_back({x, y}); } } } } return -1; }4.3 经典应用场景迷宫中的“传送门”或“滑道”某些格子走到后可以无代价移动到另一个指定位置代价0。电路板布线走直线代价小拐弯代价大可以建模为直走代价0拐弯代价1。“旋转锁”问题每次旋转一位数字某些旋转方向代价不同。解决带权图的最短路问题权值为0或1这是最直接的应用。避坑技巧实现0-1 BFS时判重数组dist的更新和入队操作必须是原子的且必须在入队前完成。即一旦计算出新状态(x, y)并通过了合法性检查就应该立即更新dist[x][y]然后根据代价w决定将其放入队头还是队尾。不能先入队等出队时再计算距离这会破坏双端队列所维护的“代价单调性”导致结果错误。这是和普通BFS实现时的一个细微但重要的区别。5. 融会贯通最小步数模型的抽象与BFS的统御“最小步数模型”是一个更上层的概念它描述了一类问题给定一个初始状态和一个目标状态以及一系列状态转移规则操作求从初始状态变换到目标状态所需的最少操作步数。这里的“状态”可以非常广泛棋盘的一个局面、魔方的一个排列、一个字符串、一个数字等等。BFS是解决最小步数模型的天然武器因为BFS搜索的层次数正好对应着从起点状态到当前状态所需的操作步数。当BFS第一次搜索到目标状态时经历的层数就是最小步数。5.1 将具体问题抽象为状态图解决这类问题的关键在于建模定义状态什么信息能唯一确定当前局面可能是坐标(x, y)可能是一个字符串可能是一个多维数组。定义状态转移边从一个状态通过一次允许的操作能到达哪些其他状态每个转移的“代价”是多少在基础BFS中通常代价都为1。定义起点和终点初始状态和目标状态。一旦完成建模整个问题就转化为在一个“状态图”中寻找从起点到终点的最短路径。图的节点是状态图的边是状态转移操作。5.2 实例分析八数码问题这是一个经典的最小步数模型。在一个3x3的棋盘上摆放着1-8的数字和一个空格。每次操作可以将空格与上下左右相邻的一个数字交换。给定一个初始布局问至少需要多少次操作能将其变成目标布局通常是12345678空。状态定义用一个字符串或9位数表示当前棋盘布局。例如”12345678 “。状态转移找到空格的位置尝试与上下左右四个方向的数字交换生成新的布局字符串。起点和终点初始布局字符串和目标布局字符串。BFS搜索从起点字符串开始BFS每次从队列中取出一个状态生成其所有可能的下一状态即交换一次后的新字符串如果未访问过则距离1并入队。直到找到目标字符串。5.3 状态空间与判重的重要性在最小步数模型中状态空间可能非常庞大。例如八数码问题状态总数是9! 362880。如果不进行判重BFS的搜索树会指数级膨胀迅速耗尽内存和时间。因此一个高效的状态判重方法至关重要。小范围状态可以使用数组或unordered_set、set来存储已访问状态。中等范围状态对于像八数码这种状态可以使用康托展开将其映射为一个唯一的整数索引然后用数组判重。极大状态空间可能需要使用哈希表或者双向BFS、A*等启发式搜索来减少搜索量。5.4 BFS变种在模型中的选择普通单源BFS适用于所有操作代价相同通常为1的模型。如走迷宫、八数码、单词接龙等。多源BFS适用于有多个起点求每个位置到最近起点距离的模型。是单源BFS的自然扩展。双端队列BFS适用于操作代价只有0和1两种的模型。它是对普通BFS在边权上的泛化。优先队列BFSDijkstra适用于操作代价为任意非负权值的模型。这是更一般的加权图最短路径算法。实操心得面对一个新的“最小步数”问题我的思考顺序是1. 状态如何表示力求简洁、唯一、易哈希2. 状态如何转移生成所有合法后继状态3. 如何判重根据状态数量选择合适数据结构4. 边权是否全为1如果不是是只有0和1还是任意权值据此选择BFS、0-1 BFS还是Dijkstra。把这个流程固化下来能帮你快速拆解绝大多数搜索问题。6. 实战演练综合案例分析与代码实现让我们通过一个综合性的例题来巩固以上概念。问题描述如下有一个n x m的网格。其中‘S’表示起点‘E’表示终点‘.’表示空地‘#’表示永久障碍‘*’表示可破坏的障碍。你有一个炸弹使用后可以永久炸掉一个‘*’障碍将其变为空地。每次移动可以向上下左右四个方向走到相邻的非‘#’格子。求从起点到终点的最短路径长度。如果无法到达输出-1。6.1 问题分析与状态定义这是一个典型的状态空间搜索问题。如果没有任何障碍就是普通BFS。现在有了可破坏的障碍‘*’关键决策在于是否使用炸弹以及何时使用。我们不能简单地把它当成普通空地因为炸弹只能用一次。这引入了“是否已使用炸弹”这个额外的状态维度。因此我们的搜索状态需要包含三维信息当前坐标(x, y)和是否已使用炸弹hasBomb。所以状态可以定义为(x, y, hasBomb)。其中hasBomb为true表示炸弹已用为false表示炸弹未用。6.2 状态转移与BFS设计从当前状态(x, y, hasBomb)出发我们可以尝试向四个方向移动如果目标格子是‘.’或‘E’可以直接走过去。新状态为(nx, ny, hasBomb)代价为1。如果目标格子是‘*’如果hasBomb false炸弹未用我们可以选择使用炸弹炸掉它然后走过去。新状态为(nx, ny, true)代价为1。如果hasBomb true炸弹已用则无法通过。如果目标格子是‘#’无法通过。我们发现所有状态转移的代价都是1。因此我们可以使用普通BFS来求解。但状态空间变成了n * m * 2。6.3 代码实现我们需要一个三维的dist数组来记录距离和判重dist[x][y][0]表示在(x, y)且未使用炸弹的最短距离dist[x][y][1]表示在(x, y)且已使用炸弹的最短距离。#include iostream #include queue #include cstring using namespace std; const int N 510; int n, m; char g[N][N]; int dist[N][N][2]; // 第三维0-未用炸弹1-已用炸弹 int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; struct State { int x, y; bool hasBomb; // 是否使用了炸弹 }; int bfs(int sx, int sy, int tx, int ty) { memset(dist, -1, sizeof dist); queueState q; q.push({sx, sy, false}); dist[sx][sy][0] 0; // 起点未用炸弹 while (!q.empty()) { State t q.front(); q.pop(); // 到达终点返回距离。由于BFS第一次找到就是最短。 if (t.x tx t.y ty) { // 终点状态可能有两种取到达时任意一种的距离即可因为BFS保证最短 // 更严谨的做法是遍历hasBomb的两种状态取最小值但这里首次到达即最优 return dist[t.x][t.y][t.hasBomb]; } for (int i 0; i 4; i) { int nx t.x dx[i]; int ny t.y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; char cell g[nx][ny]; bool nextBomb t.hasBomb; bool canMove false; if (cell . || cell E) { canMove true; } else if (cell *) { if (!t.hasBomb) { // 可以炸掉障碍 canMove true; nextBomb true; // 使用炸弹 } else { canMove false; // 已用过炸弹无法通过 } } else if (cell #) { canMove false; } if (canMove dist[nx][ny][nextBomb] -1) { dist[nx][ny][nextBomb] dist[t.x][t.y][t.hasBomb] 1; q.push({nx, ny, nextBomb}); } } } return -1; } int main() { // 假设已读入n, m和地图g并找到起点(sx, sy)和终点(tx, ty) int sx, sy, tx, ty; // ... 读入和查找起点终点的代码 ... int ans bfs(sx, sy, tx, ty); cout ans endl; return 0; }6.4 案例总结这个案例完美展示了如何将复杂问题转化为BFS可解的最小步数模型识别状态维度除了坐标还有“炸弹使用状态”这个关键信息。设计状态表示使用结构体State和三维dist数组。厘清状态转移规则针对不同格子类型和当前状态决定下一步的状态和代价。套用BFS框架一旦状态和转移定义清楚剩下的就是标准的BFS流程。常见问题在类似这种带额外状态的问题中最容易出错的地方是状态判重。我们必须用dist[x][y][hasBomb]来精确记录在特定hasBomb条件下到达(x, y)的最短距离。不能只用dist[x][y]因为从不同路径到达(x, y)hasBomb可能不同这代表了完全不同的后续决策能力。例如一条路径是没用炸弹绕远路过来的另一条是用过炸弹抄近路过来的。虽然坐标相同但它们是两个不同的状态必须分开处理。7. 性能优化与边界处理让BFS更加稳健高效当问题规模变大或者状态空间复杂时基础的BFS可能会面临性能瓶颈甚至错误。这里分享一些关键的优化技巧和边界情况处理方法。7.1 判重数据结构的选择判重是BFS正确性的基石其数据结构的选择直接影响性能。数组 (dist)最优选择当状态可以映射到一个连续的整数范围时如网格坐标、康托展开值。访问是O(1)。unordered_set(哈希集合)当状态是一个复杂对象如字符串、向量时使用。平均O(1)访问但需要为状态编写哈希函数。set(红黑树集合)当状态无法高效哈希或需要有序遍历时使用。访问是O(log n)比unordered_set慢。布隆过滤器在允许极低概率误判的海量数据去重场景下使用算法竞赛中较少见。选择原则优先使用数组其次unordered_set最后考虑set。7.2 双向BFSBidirectional BFS当起点和终点都明确且状态空间巨大时双向BFS可以显著减少搜索范围。其思想是从起点和终点同时开始BFS当两个搜索的“前沿”相遇时路径找到。搜索的节点数从O(b^d)减少到O(b^{d/2})其中b是分支因子d是路径深度。实现要点使用两个队列和两个dist数组或一个数组但用不同值标记来源。每次迭代选择节点数更少的那一端进行扩展以平衡搜索。检查新扩展的节点是否已经被另一端的搜索访问过如果是则找到路径。路径长度为dist_start[current] dist_end[current] 1。7.3 边界条件与初始化陷阱起点即终点在BFS开始前首先判断if (sx tx sy ty) return 0;。这是一个常见的优化和正确性保障。不可达判断BFS结束后如果终点的dist值仍是初始值如-1则返回-1或特定标识。大数组初始化使用memset初始化数组时注意sizeof的用法。对于动态分配的二维数组不能直接sizeof(dist)。对于全局数组memset(dist, -1, sizeof dist)是安全的。队列清空在多次调用BFS的函数中如果队列是局部变量则每次会新建。如果是全局变量务必在函数开始时清空队列 (while(!q.empty()) q.pop();)。7.4 空间优化技巧状态压缩如果状态中的某些维度是布尔值或小范围整数可以考虑用位运算压缩到一个整数里。例如刚才的炸弹问题hasBomb可以用整数的最后一位表示状态变为(x, y, state)其中state 1表示炸弹状态。使用pair或tuple对于简单状态使用pairint, int或tupleint, int, int比定义结构体更方便但可读性稍差。dist数组复用在多组测试数据中如果数组很大反复memset可能耗时。可以维护一个时间戳int vis[N][N]和一个当前标记int tag。每次访问时检查vis[x][y] tag来判断是否为本轮访问访问后设置vis[x][y] tag。每轮BFS开始时tag。这样可以避免对整个大数组进行重置。性能调优实录在一次在线比赛中我遇到了一个状态空间为500*500*4的BFS问题。最初使用dist数组为int类型并且每次调用BFS都memset整个数组导致了超时。我做了两点优化1. 将dist改为short类型因为步数不会超过65535减少了内存占用和memset时间。2. 改用时间戳法判重完全避免了memset。最终顺利通过。这个故事告诉我们在极限情况下每一个细节都值得优化。 从单源到多源与0-1 BFS：最短路径搜索算法的演进与实战
1. 从单点到全局BFS算法的核心思想与演进如果你刷过一些算法题或者接触过图论、搜索相关的知识BFS广度优先搜索这个名字你一定不陌生。它就像一位训练有素的侦察兵从起点出发以“一圈一圈”向外探索的方式确保找到的路径是最短的。经典的BFS模型比如走迷宫找最短路径我们通常只设置一个起点然后逐层扩散。这个模型直观、强大是很多算法初学者的必修课。但真实世界的问题往往更复杂。想象一下森林里多处同时起火消防队需要知道火势蔓延到每个位置的最短时间或者在一个社交网络中多个核心用户同时发布消息计算信息到达每个用户的最短路径。这些问题不再是“从一个点出发”而是“从多个点同时出发”。这就是多源BFS要解决的问题。它不再是单个侦察兵而是一支同时从多个基地出发的侦察小队协同绘制整个区域的地图。更进一步在有些场景下每一步的“代价”并不相同。在经典的网格BFS中向上下左右四个方向移动一格代价都是1。但如果我告诉你有些方向移动代价是0比如平地滑行有些方向移动代价是1比如正常行走甚至有些是2比如攀爬我们如何找到总代价最小的路径这就需要引入双端队列广搜也叫0-1 BFS。它像是给侦察兵配备了不同的交通工具在代价不同的道路上采用更聪明的策略进行探索。而最小步数模型则是这类问题最经典的抽象和表述。它不关心你是走迷宫、推箱子还是滑动拼图它只关心从一个初始状态通过一系列允许的操作每一步可能代价相同也可能不同变换到目标状态最少需要多少步。BFS及其变种正是解决这类问题的利器。理解从单源BFS到多源BFS再到双端队列BFS的演进不仅仅是多学几个算法模板更是对“状态搜索”这一核心思想的深化。它能让你在面对各种“最短步数”、“最小代价”问题时迅速识别模型选择最合适的工具写出高效而优雅的代码。接下来我们就层层拆解看看这些“侦察兵”是如何升级装备、改变战术的。2. 温故知新经典单源BFS的核心框架与“最短”的保证在深入高级变种之前我们必须牢牢夯实单源BFS的基础。它的核心思想可以用一句话概括由近及远层层扩展。算法使用一个队列Queue来维护待访问的节点遵循“先进先出”的原则这天然保证了距离起点近的节点会优先被访问。我们以一个经典的二维网格迷宫为例。假设在一个n x m的网格中‘.’代表可通行的空地‘#’代表障碍物我们从起点(sx, sy)出发希望找到到达终点(tx, ty)的最短步数。每次可以向上下左右四个方向移动一格。2.1 标准代码框架与逐行解析下面是一个极具代表性的C实现框架几乎可以套用于所有网格类单源最短路径问题#include iostream #include queue #include cstring using namespace std; typedef pairint, int PII; // 用pair存储坐标(x, y) const int N 1010; // 根据问题规模定义 int n, m; char g[N][N]; // 存储网格地图 int dist[N][N]; // 存储从起点到每个点的最短距离同时兼作visited数组 // 四个方向向量上、右、下、左 int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; int bfs(int sx, int sy, int tx, int ty) { // 初始化距离数组为-1表示未访问 memset(dist, -1, sizeof dist); queuePII q; // 起点入队并标记 q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { auto t q.front(); q.pop(); // 如果到达终点直接返回距离。由于BFS特性第一次到达就是最短距离。 if (t.first tx t.second ty) { return dist[tx][ty]; } // 遍历四个方向 for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; // 核心判断逻辑1.不越界 2.不是障碍 3.未被访问过 if (x 0 x n y 0 y m g[x][y] ! # dist[x][y] -1) { // 新点的距离等于当前点距离1 dist[x][y] dist[t.first][t.second] 1; q.push({x, y}); } } } // 队列为空仍未找到终点说明终点不可达 return -1; }为什么这个框架能保证找到最短路径关键在于队列的“先进先出”和距离数组dist的更新方式。起点距离为0入队。然后所有距离起点为1的节点会在第一轮循环中被发现并入队它们的dist被设为1。接着当处理这些距离为1的节点时会发现所有距离为2的节点且未被访问过的……如此往复。因为队列保证了距离为d的所有节点一定在距离为d1的节点之前被处理所以当第一次搜索到终点时其dist值必然是最小的。2.2 关键细节与避坑指南状态判重是生命线dist数组在这里扮演了双重角色记录最短距离和标记是否已访问。dist[x][y] ! -1就意味着这个点已经被更早或同等距离访问过。忘记判重是BFS导致死循环或结果错误的最常见原因。想象一下如果不判重A点走到B点B点又走回A点算法就会在这两点间无限循环。在出队时判断终点 vs 在入队时判断终点上面的代码是在从队列中取出节点q.front()时判断是否为终点。这没有问题因为BFS保证第一次取到终点时距离最短。你也可以在将新节点入队前判断逻辑上是等价的。但绝对不能在刚计算出新坐标(x, y)时就立刻返回因为此时还没有为这个点计算dist值或者计算可能不完整。距离数组的初始化memset(dist, -1, sizeof dist)将距离初始化为-1这是一个非常实用的技巧。-1明确表示“未访问”而任何非负整数都表示一个有效距离。这比单独使用一个bool visited数组更简洁。方向向量的运用使用dx[4]和dy[4]数组来定义方向比写四个独立的if语句更优雅也更不容易出错。当需要处理八方向包括对角线时这个技巧的优势更加明显。实操心得在竞赛或面试中我习惯将BFS封装成一个返回int最短步数或vector路径的函数。dist数组一定要开成全局变量或在堆上分配避免在函数内开大数组导致栈溢出。对于n, m在几百以上的网格局部数组非常危险。3. 化繁为简多源BFS的建模思路与高效实现现在我们来升级问题。不再是单一火源而是多处同时起火。我们想知道火蔓延到每个空地的最短时间。最笨的办法是对每个火源都跑一遍单源BFS然后对每个空地取所有BFS结果的最小值。时间复杂度是O(k * n * m)k是火源数量这显然不够高效。多源BFS提供了一个O(n * m)的优美解法。其核心思想是在初始化队列时将所有“源点”一次性全部加入队列并设置好它们的初始距离通常为0。然后就像普通的BFS一样进行扩展。3.1 算法步骤拆解初始化创建一个距离数组dist初始化为-1表示未到达。创建一个队列q。多源入队遍历整个网格将所有火源点或多个起点的坐标加入队列并将这些点在dist中的值设为0。标准BFS扩展开始标准的BFS循环。每次从队头取出一个点检查其四个邻居。如果邻居是空地且未被访问过dist为-1则将其dist更新为当前点dist 1并将其入队。结果当BFS结束后dist数组中就存储了每个空地距离最近火源的最短蔓延时间。对于障碍物或火源点本身可以根据需要特殊处理。3.2 为什么这样是对的我们可以把多个源点想象成在“第0层”同时存在。BFS的第一轮扩展会找出所有距离任意一个源点距离为1的点。这些点会被标记距离1并入队。接下来从这些距离为1的点扩展会得到所有距离为2的点……这个过程和单源BFS完全一致只不过初始的“波前”不再是一个点而是一个点集。由于BFS的层次扩展特性每个点第一次被访问时一定是被离它最近的那个源点访问到的因此记录的距离就是最短距离。3.3 代码实现对比我们修改之前的bfs函数使其适应多源。假设火源点在地图中用‘F’表示。// dist数组存储每个点到最近火源的距离 void multiSourceBfs() { memset(dist, -1, sizeof dist); queuePII q; // 步骤1: 找到所有源点并加入队列 for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] F) { // 找到火源 q.push({i, j}); dist[i][j] 0; // 火源本身距离为0 } } } // 步骤2: 标准BFS过程 while (!q.empty()) { auto t q.front(); q.pop(); for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; if (x 0 x n y 0 y m g[x][y] . dist[x][y] -1) { dist[x][y] dist[t.first][t.second] 1; q.push({x, y}); } } } }执行完这个函数后对于任意一个空地(i, j)dist[i][j]就代表了火蔓延到该处所需的最短时间。如果dist[i][j] -1说明该点被障碍物包围火永远无法蔓延到。3.4 典型应用场景与扩展森林大火蔓延模拟如上所述。多个起点的最短路径问题例如在一个地图上有多个快递站求每个居民楼到最近快递站的距离。岛屿问题变种求所有海洋格子到最近陆地的距离LeetCode 1162. 地图分析。“广播”问题多个消息源同时广播求消息到达每个节点的最短时间。注意事项多源BFS的“源点”在初始时是平权的即它们的初始距离相同通常为0。如果源点具有不同的初始“强度”或“起始距离”需要在入队时赋予不同的dist初始值。这时队列中初始就包含了不同层次的点但BFS的过程依然能保证正确性因为队列保证了距离小的点优先被处理前提是所有边的权重非负且相等这里是1。如果边权不同则需要用到优先队列BFS的进一步升级——Dijkstra算法这超出了本文基础BFS的范畴。4. 代价分化双端队列广搜0-1 BFS的原理与降维打击现在让我们进入BFS的另一个进阶形态双端队列广搜Deque BFS它特别擅长解决边权只有两种值通常是0和1的最短路径问题。考虑这样一个问题在一个网格中你可以向上下左右四个方向移动。但是向上和向下移动不消耗步数代价为0向左和向右移动消耗1步代价为1。求从起点到终点的最小代价。如果用普通BFS我们无法处理代价为0的边。因为BFS的队列认为每一层扩展代价都是1。如果用Dijkstra算法可以解决但杀鸡用牛刀时间复杂度是O(E log V)。0-1 BFS提供了一个O(V E)的线性解法。其核心在于使用一个双端队列Deque来代替普通队列并修改入队策略如果通过一条代价为0的边到达一个新节点就将这个新节点从队头插入。如果通过一条代价为1的边到达一个新节点就将这个新节点从队尾插入。4.1 算法正确性直观理解你可以把双端队列想象成一个“两端都能进出的管道”。从队头取出的元素我们认为是当前“代价最小”的待处理节点。初始时起点代价0在队头。当我们通过代价0的边扩展时新节点的代价和当前节点相同。为了让它们能尽快被处理我们将其压入队头。这样下一轮循环就会优先处理这些代价不变的节点保持了“优先扩展代价小节点”的顺序。当我们通过代价1的边扩展时新节点的代价比当前节点大1。我们将其压入队尾就像普通BFS一样。这个过程本质上是在模拟一个“简化版的Dijkstra算法”。由于边权只有0和1我们不需要复杂的优先队列堆只需要一个双端队列就能维持节点的“优先级”顺序。4.2 代码框架示例假设grid[x][y]存储了该点的类型0代表代价为0的移动可达1代表代价为1的移动可达。我们用一个deque来维护队列。#include deque // ... 其他头文件和定义 int zeroOneBfs(int sx, int sy, int tx, int ty) { memset(dist, -1, sizeof dist); dequePII dq; // 使用双端队列 dq.push_front({sx, sy}); // 起点从队头入队 dist[sx][sy] 0; while (!dq.empty()) { auto t dq.front(); dq.pop_front(); // 找到终点即可返回因为队头保证当前最小代价 if (t.first tx t.second ty) { return dist[tx][ty]; } // 假设有四个方向代价存储在cost[4]数组中值为0或1 int cost[4] {0, 1, 0, 1}; // 示例上(0), 右(1), 下(0), 左(1) for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; int w cost[i]; // 本次移动的代价 if (x 0 x n y 0 y m grid[x][y]是可通行的 dist[x][y] -1) { dist[x][y] dist[t.first][t.second] w; if (w 0) { // 代价为0插入队头 dq.push_front({x, y}); } else { // w 1 // 代价为1插入队尾 dq.push_back({x, y}); } } } } return -1; }4.3 经典应用场景迷宫中的“传送门”或“滑道”某些格子走到后可以无代价移动到另一个指定位置代价0。电路板布线走直线代价小拐弯代价大可以建模为直走代价0拐弯代价1。“旋转锁”问题每次旋转一位数字某些旋转方向代价不同。解决带权图的最短路问题权值为0或1这是最直接的应用。避坑技巧实现0-1 BFS时判重数组dist的更新和入队操作必须是原子的且必须在入队前完成。即一旦计算出新状态(x, y)并通过了合法性检查就应该立即更新dist[x][y]然后根据代价w决定将其放入队头还是队尾。不能先入队等出队时再计算距离这会破坏双端队列所维护的“代价单调性”导致结果错误。这是和普通BFS实现时的一个细微但重要的区别。5. 融会贯通最小步数模型的抽象与BFS的统御“最小步数模型”是一个更上层的概念它描述了一类问题给定一个初始状态和一个目标状态以及一系列状态转移规则操作求从初始状态变换到目标状态所需的最少操作步数。这里的“状态”可以非常广泛棋盘的一个局面、魔方的一个排列、一个字符串、一个数字等等。BFS是解决最小步数模型的天然武器因为BFS搜索的层次数正好对应着从起点状态到当前状态所需的操作步数。当BFS第一次搜索到目标状态时经历的层数就是最小步数。5.1 将具体问题抽象为状态图解决这类问题的关键在于建模定义状态什么信息能唯一确定当前局面可能是坐标(x, y)可能是一个字符串可能是一个多维数组。定义状态转移边从一个状态通过一次允许的操作能到达哪些其他状态每个转移的“代价”是多少在基础BFS中通常代价都为1。定义起点和终点初始状态和目标状态。一旦完成建模整个问题就转化为在一个“状态图”中寻找从起点到终点的最短路径。图的节点是状态图的边是状态转移操作。5.2 实例分析八数码问题这是一个经典的最小步数模型。在一个3x3的棋盘上摆放着1-8的数字和一个空格。每次操作可以将空格与上下左右相邻的一个数字交换。给定一个初始布局问至少需要多少次操作能将其变成目标布局通常是12345678空。状态定义用一个字符串或9位数表示当前棋盘布局。例如”12345678 “。状态转移找到空格的位置尝试与上下左右四个方向的数字交换生成新的布局字符串。起点和终点初始布局字符串和目标布局字符串。BFS搜索从起点字符串开始BFS每次从队列中取出一个状态生成其所有可能的下一状态即交换一次后的新字符串如果未访问过则距离1并入队。直到找到目标字符串。5.3 状态空间与判重的重要性在最小步数模型中状态空间可能非常庞大。例如八数码问题状态总数是9! 362880。如果不进行判重BFS的搜索树会指数级膨胀迅速耗尽内存和时间。因此一个高效的状态判重方法至关重要。小范围状态可以使用数组或unordered_set、set来存储已访问状态。中等范围状态对于像八数码这种状态可以使用康托展开将其映射为一个唯一的整数索引然后用数组判重。极大状态空间可能需要使用哈希表或者双向BFS、A*等启发式搜索来减少搜索量。5.4 BFS变种在模型中的选择普通单源BFS适用于所有操作代价相同通常为1的模型。如走迷宫、八数码、单词接龙等。多源BFS适用于有多个起点求每个位置到最近起点距离的模型。是单源BFS的自然扩展。双端队列BFS适用于操作代价只有0和1两种的模型。它是对普通BFS在边权上的泛化。优先队列BFSDijkstra适用于操作代价为任意非负权值的模型。这是更一般的加权图最短路径算法。实操心得面对一个新的“最小步数”问题我的思考顺序是1. 状态如何表示力求简洁、唯一、易哈希2. 状态如何转移生成所有合法后继状态3. 如何判重根据状态数量选择合适数据结构4. 边权是否全为1如果不是是只有0和1还是任意权值据此选择BFS、0-1 BFS还是Dijkstra。把这个流程固化下来能帮你快速拆解绝大多数搜索问题。6. 实战演练综合案例分析与代码实现让我们通过一个综合性的例题来巩固以上概念。问题描述如下有一个n x m的网格。其中‘S’表示起点‘E’表示终点‘.’表示空地‘#’表示永久障碍‘*’表示可破坏的障碍。你有一个炸弹使用后可以永久炸掉一个‘*’障碍将其变为空地。每次移动可以向上下左右四个方向走到相邻的非‘#’格子。求从起点到终点的最短路径长度。如果无法到达输出-1。6.1 问题分析与状态定义这是一个典型的状态空间搜索问题。如果没有任何障碍就是普通BFS。现在有了可破坏的障碍‘*’关键决策在于是否使用炸弹以及何时使用。我们不能简单地把它当成普通空地因为炸弹只能用一次。这引入了“是否已使用炸弹”这个额外的状态维度。因此我们的搜索状态需要包含三维信息当前坐标(x, y)和是否已使用炸弹hasBomb。所以状态可以定义为(x, y, hasBomb)。其中hasBomb为true表示炸弹已用为false表示炸弹未用。6.2 状态转移与BFS设计从当前状态(x, y, hasBomb)出发我们可以尝试向四个方向移动如果目标格子是‘.’或‘E’可以直接走过去。新状态为(nx, ny, hasBomb)代价为1。如果目标格子是‘*’如果hasBomb false炸弹未用我们可以选择使用炸弹炸掉它然后走过去。新状态为(nx, ny, true)代价为1。如果hasBomb true炸弹已用则无法通过。如果目标格子是‘#’无法通过。我们发现所有状态转移的代价都是1。因此我们可以使用普通BFS来求解。但状态空间变成了n * m * 2。6.3 代码实现我们需要一个三维的dist数组来记录距离和判重dist[x][y][0]表示在(x, y)且未使用炸弹的最短距离dist[x][y][1]表示在(x, y)且已使用炸弹的最短距离。#include iostream #include queue #include cstring using namespace std; const int N 510; int n, m; char g[N][N]; int dist[N][N][2]; // 第三维0-未用炸弹1-已用炸弹 int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; struct State { int x, y; bool hasBomb; // 是否使用了炸弹 }; int bfs(int sx, int sy, int tx, int ty) { memset(dist, -1, sizeof dist); queueState q; q.push({sx, sy, false}); dist[sx][sy][0] 0; // 起点未用炸弹 while (!q.empty()) { State t q.front(); q.pop(); // 到达终点返回距离。由于BFS第一次找到就是最短。 if (t.x tx t.y ty) { // 终点状态可能有两种取到达时任意一种的距离即可因为BFS保证最短 // 更严谨的做法是遍历hasBomb的两种状态取最小值但这里首次到达即最优 return dist[t.x][t.y][t.hasBomb]; } for (int i 0; i 4; i) { int nx t.x dx[i]; int ny t.y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; char cell g[nx][ny]; bool nextBomb t.hasBomb; bool canMove false; if (cell . || cell E) { canMove true; } else if (cell *) { if (!t.hasBomb) { // 可以炸掉障碍 canMove true; nextBomb true; // 使用炸弹 } else { canMove false; // 已用过炸弹无法通过 } } else if (cell #) { canMove false; } if (canMove dist[nx][ny][nextBomb] -1) { dist[nx][ny][nextBomb] dist[t.x][t.y][t.hasBomb] 1; q.push({nx, ny, nextBomb}); } } } return -1; } int main() { // 假设已读入n, m和地图g并找到起点(sx, sy)和终点(tx, ty) int sx, sy, tx, ty; // ... 读入和查找起点终点的代码 ... int ans bfs(sx, sy, tx, ty); cout ans endl; return 0; }6.4 案例总结这个案例完美展示了如何将复杂问题转化为BFS可解的最小步数模型识别状态维度除了坐标还有“炸弹使用状态”这个关键信息。设计状态表示使用结构体State和三维dist数组。厘清状态转移规则针对不同格子类型和当前状态决定下一步的状态和代价。套用BFS框架一旦状态和转移定义清楚剩下的就是标准的BFS流程。常见问题在类似这种带额外状态的问题中最容易出错的地方是状态判重。我们必须用dist[x][y][hasBomb]来精确记录在特定hasBomb条件下到达(x, y)的最短距离。不能只用dist[x][y]因为从不同路径到达(x, y)hasBomb可能不同这代表了完全不同的后续决策能力。例如一条路径是没用炸弹绕远路过来的另一条是用过炸弹抄近路过来的。虽然坐标相同但它们是两个不同的状态必须分开处理。7. 性能优化与边界处理让BFS更加稳健高效当问题规模变大或者状态空间复杂时基础的BFS可能会面临性能瓶颈甚至错误。这里分享一些关键的优化技巧和边界情况处理方法。7.1 判重数据结构的选择判重是BFS正确性的基石其数据结构的选择直接影响性能。数组 (dist)最优选择当状态可以映射到一个连续的整数范围时如网格坐标、康托展开值。访问是O(1)。unordered_set(哈希集合)当状态是一个复杂对象如字符串、向量时使用。平均O(1)访问但需要为状态编写哈希函数。set(红黑树集合)当状态无法高效哈希或需要有序遍历时使用。访问是O(log n)比unordered_set慢。布隆过滤器在允许极低概率误判的海量数据去重场景下使用算法竞赛中较少见。选择原则优先使用数组其次unordered_set最后考虑set。7.2 双向BFSBidirectional BFS当起点和终点都明确且状态空间巨大时双向BFS可以显著减少搜索范围。其思想是从起点和终点同时开始BFS当两个搜索的“前沿”相遇时路径找到。搜索的节点数从O(b^d)减少到O(b^{d/2})其中b是分支因子d是路径深度。实现要点使用两个队列和两个dist数组或一个数组但用不同值标记来源。每次迭代选择节点数更少的那一端进行扩展以平衡搜索。检查新扩展的节点是否已经被另一端的搜索访问过如果是则找到路径。路径长度为dist_start[current] dist_end[current] 1。7.3 边界条件与初始化陷阱起点即终点在BFS开始前首先判断if (sx tx sy ty) return 0;。这是一个常见的优化和正确性保障。不可达判断BFS结束后如果终点的dist值仍是初始值如-1则返回-1或特定标识。大数组初始化使用memset初始化数组时注意sizeof的用法。对于动态分配的二维数组不能直接sizeof(dist)。对于全局数组memset(dist, -1, sizeof dist)是安全的。队列清空在多次调用BFS的函数中如果队列是局部变量则每次会新建。如果是全局变量务必在函数开始时清空队列 (while(!q.empty()) q.pop();)。7.4 空间优化技巧状态压缩如果状态中的某些维度是布尔值或小范围整数可以考虑用位运算压缩到一个整数里。例如刚才的炸弹问题hasBomb可以用整数的最后一位表示状态变为(x, y, state)其中state 1表示炸弹状态。使用pair或tuple对于简单状态使用pairint, int或tupleint, int, int比定义结构体更方便但可读性稍差。dist数组复用在多组测试数据中如果数组很大反复memset可能耗时。可以维护一个时间戳int vis[N][N]和一个当前标记int tag。每次访问时检查vis[x][y] tag来判断是否为本轮访问访问后设置vis[x][y] tag。每轮BFS开始时tag。这样可以避免对整个大数组进行重置。性能调优实录在一次在线比赛中我遇到了一个状态空间为500*500*4的BFS问题。最初使用dist数组为int类型并且每次调用BFS都memset整个数组导致了超时。我做了两点优化1. 将dist改为short类型因为步数不会超过65535减少了内存占用和memset时间。2. 改用时间戳法判重完全避免了memset。最终顺利通过。这个故事告诉我们在极限情况下每一个细节都值得优化。