前言广度优先搜索breadth-first search, BFS是从起点出发按「距离起点的边数」一层一层向外扩展的遍历算法。它最典型的应用是求无权图或边权全为 1 的图上的最短路径第一次到达某个结点时经过的边数就是起点到它的最短距离。这里先澄清一个常见的分类混淆有些资料把「回溯算法」和「广度优先搜索」并列成两类算法这种说法并不准确。回溯backtracking通常是深度优先搜索DFS的一种强调「做出选择、递归、撤销选择」用来枚举所有可行解BFS 则是按层扩展强调「先访问距离近的结点」天然适合求最短路。两者不是同一维度的对立概念一道题可以用 DFS 回溯枚举所有路径也可以用 BFS 找最短路径取决于问的是「有多少种走法」还是「最少几步」。本文用网格迷宫为例讲清 BFS 的队列框架、访问标记的时机、路径还原以及多源 BFS 和 0-1 BFS 两个常见变体。代码以 C17 为基准。一、BFS 的基本框架BFS 需要三样东西一个队列存放「待扩展」的结点。一个访问标记防止同一个结点被重复入队。可选的层数或距离数组。框架如下// 适用于 C17#include queue#include vectorvoid bfs(int start, const std::vectorstd::vectorint adj) {std::vectorbool visited(adj.size(), false);std::queueint q;visited[start] true;q.push(start);while (!q.empty()) {int u q.front();q.pop();for (int v : adj[u]) {if (!visited[v]) {visited[v] true; // 入队时立即标记q.push(v);}}}}关键点是visited[v] true;放在q.push(v);之前。如果放到出队时再标记同一个结点可能被多个邻居重复入队队列会膨胀虽然结果仍然正确但效率变差某些图上甚至会出现指数级的重复。BFS 的复杂度是 O(V E)每个结点最多入队一次每条边最多被检查两次无向图。空间是 O(V)主要花在队列和访问数组上。二、为什么 BFS 能求无权最短路设起点为s。BFS 按「与s的距离」分层先访问距离 0 的s再访问距离 1 的所有结点再访问距离 2 的结点依此类推。队列的先进先出特性保证了这一点距离小的结点先入队也会先出队。当第一次访问结点v时它是由某个距离为d的结点u扩展来的所以v的距离是d 1。如果存在一条更短的路径那么路径上的前驱结点距离更小应该更早被访问v也应该更早入队——这与「第一次访问」矛盾。因此第一次访问时的距离就是最短距离。这个论证依赖「边权相同」。如果边权不同BFS 按边数分层就不再等于按距离分层需要用 Dijkstra 算法如果边权只有 0 和 1可以用 0-1 BFS双端队列。三、网格迷宫实例给定一个R × C的网格0表示可走1表示障碍。从起点s走到终点t每步可以上下左右移动一格求最少步数并输出一条路径。// 适用于 C17#include algorithm#include iostream#include queue#include vectorstruct Point {int r;int c;};int bfsMaze(const std::vectorstd::vectorint grid,Point start, Point target,std::vectorPoint path) {const int rows static_castint(grid.size());const int cols static_castint(grid[0].size());std::vectorstd::vectorint dist(rows, std::vectorint(cols, -1));std::vectorstd::vectorPoint parent(rows, std::vectorPoint(cols, {-1, -1}));std::queuePoint q;dist[start.r][start.c] 0;q.push(start);const int dr[4] {-1, 1, 0, 0};const int dc[4] {0, 0, -1, 1};while (!q.empty()) {Point cur q.front();q.pop();if (cur.r target.r cur.c target.c) break;for (int d 0; d 4; d) {const int nr cur.r dr[d];const int nc cur.c dc[d];if (nr 0 || nr rows || nc 0 || nc cols) continue;if (grid[nr][nc] 1) continue;if (dist[nr][nc] ! -1) continue;dist[nr][nc] dist[cur.r][cur.c] 1;parent[nr][nc] cur;q.push({nr, nc});}}if (dist[target.r][target.c] -1) {return -1;}path.clear();Point cur target;while (!(cur.r start.r cur.c start.c)) {path.push_back(cur);cur parent[cur.r][cur.c];}path.push_back(start);std::reverse(path.begin(), path.end());return dist[target.r][target.c];}逐处说明dist初始化为 -1既表示「未访问」也用来存距离。用 -1 而不是INT_MAX可以少一个「是否访问」的数组。parent记录每个结点是从哪个结点扩展来的用于还原路径。起点没有前驱初始化为{-1, -1}但还原循环在到达起点时就停止不会读取它。入队前做三重检查越界、障碍、已访问。顺序可以调整但越界检查必须在访问grid[nr][nc]之前。找到终点后break只是提前结束扩展dist和parent已经记录了最短路径可以直接还原。还原时从终点沿parent往回走最后反转。因为每个结点只有一个前驱路径是唯一的在 BFS 的访问顺序下。grid[0].size()的前提是grid非空。调用方需要保证至少有一行一列更稳妥的写法是函数开头判断grid.empty() || grid[0].empty()。四、多源 BFS有些问题有多个起点要求每个格子到「最近起点」的距离。做法是把所有起点同时入队dist初始化为 0然后正常 BFS。因为队列的先进先出距离相同的起点会一起扩展第一次到达某个格子时的距离就是它到最近起点的距离。// 适用于 C17std::vectorstd::vectorint multiSourceBfs(const std::vectorstd::vectorint grid,const std::vectorPoint sources) {const int rows static_castint(grid.size());const int cols static_castint(grid[0].size());std::vectorstd::vectorint dist(rows, std::vectorint(cols, -1));std::queuePoint q;for (const Point p : sources) {if (grid[p.r][p.c] 1) continue;dist[p.r][p.c] 0;q.push(p);}const int dr[4] {-1, 1, 0, 0};const int dc[4] {0, 0, -1, 1};while (!q.empty()) {Point cur q.front();q.pop();for (int d 0; d 4; d) {const int nr cur.r dr[d];const int nc cur.c dc[d];if (nr 0 || nr rows || nc 0 || nc cols) continue;if (grid[nr][nc] 1 || dist[nr][nc] ! -1) continue;dist[nr][nc] dist[cur.r][cur.c] 1;q.push({nr, nc});}}return dist;}多源 BFS 的正确性来自「虚拟超级源点」想象一个额外的源点到所有真实起点的距离都是 0从它出发做普通 BFS效果与把所有起点先入队完全相同。五、0-1 BFS如果边权只有 0 和 1可以用双端队列std::deque代替普通队列边权为 0 时把新结点放到队首边权为 1 时放到队尾。这样队列仍然保持「距离非降」的顺序第一次出队时的距离就是最短距离。// 适用于 C17#include deque#include limitsint zeroOneBfs(int start, int target,const std::vectorstd::vectorstd::pairint, int adj) {const int n static_castint(adj.size());const int INF std::numeric_limitsint::max();std::vectorint dist(n, INF);std::dequeint dq;dist[start] 0;dq.push_front(start);while (!dq.empty()) {int u dq.front();dq.pop_front();for (const auto [v, w] : adj[u]) {if (dist[u] ! INF dist[u] w dist[v]) {dist[v] dist[u] w;if (w 0) dq.push_front(v);else dq.push_back(v);}}}return dist[target] INF ? -1 : dist[target];}这个写法的一个细节是同一个结点可能多次入队距离被更新时出队时也没有「已确定」的标记。严格的 0-1 BFS 通常配合visited或允许重复松弛复杂度仍是 O(V E)但实现细节要小心。对边权非负的一般图应该用 Dijkstra。场景算法数据结构无权图最短路BFSstd::queue边权为 0/10-1 BFSstd::deque边权非负Dijkstrastd::priority_queue多起点多源 BFSstd::queue带负权Bellman-Ford / SPFA队列/边表常见坑点1. 出队时才标记访问❌q.pop(); if (visited[u]) continue; visited[u] true;✅ 入队前标记这样每个结点最多入队一次。2. 越界检查放在访问数组之后❌if (grid[nr][nc] 1) continue;写在范围检查之前。✅ 先判断nr、nc的范围再访问grid。3. 用 BFS 求带权图最短路❌ 边权有 2、3 等不同值时仍用普通队列。✅ 用 Dijkstra边权只有 0/1 时用 0-1 BFS。4. 忘记判断终点不可达❌ 直接返回dist[target]未访问时是 -1 或INF调用方误以为是距离。✅ 显式判断并返回约定的「不可达」值。5. 路径还原时漏掉起点❌while (cur ! start) { path.push_back(cur); cur parent[cur]; }之后没有加入起点。✅ 循环结束后path.push_back(start);再反转。6. 多源 BFS 只入队一个起点❌ 对每个起点分别跑一次 BFS再取最小值复杂度成倍增加。✅ 所有起点同时入队一次 BFS 完成。7. 用vectorbool之外的结构存距离却忘记初始化❌std::vectorstd::vectorint dist(rows, std::vectorint(cols));默认是 0和「未访问」混淆。✅ 初始化为 -1 或INF与有效距离区分开。8. 认为 BFS 能枚举所有路径❌ 用 BFS 统计从起点到终点的所有路径条数却只保留第一次访问。✅ 枚举路径用 DFS 回溯BFS 适合最短路和按层统计。总结要点结论数据结构std::queue访问标记入队时标记避免重复入队适用无权图最短路、按层遍历复杂度O(V E)空间O(V)路径还原parent数组 反向追溯变体多源 BFS、0-1 BFSBFS 的代码模板很短真正决定正确性的是两个顺序先判断边界再访问数组先标记再入队。把这两个顺序写对再根据边权选择普通队列、双端队列还是优先队列绝大多数「最短步数」类问题都能套用同一套框架。