企业官网建设流程全解析

前言

广度优先搜索（breadth-first search, BFS）是从起点出发，按「距离起点的边数」一层一层向外扩展的遍历算法。它最典型的应用是求无权图（或边权全为 1 的图）上的最短路径：第一次到达某个结点时经过的边数，就是起点到它的最短距离。

这里先澄清一个常见的分类混淆：有些资料把「回溯算法」和「广度优先搜索」并列成两类算法，这种说法并不准确。回溯（backtracking）通常是深度优先搜索（DFS）的一种，强调「做出选择、递归、撤销选择」，用来枚举所有可行解；BFS 则是按层扩展，强调「先访问距离近的结点」，天然适合求最短路。两者不是同一维度的对立概念，一道题可以用 DFS 回溯枚举所有路径，也可以用 BFS 找最短路径，取决于问的是「有多少种走法」还是「最少几步」。

本文用网格迷宫为例，讲清 BFS 的队列框架、访问标记的时机、路径还原，以及多源 BFS 和 0-1 BFS 两个常见变体。代码以 C++17 为基准。

一、BFS 的基本框架

BFS 需要三样东西：

1. 
   
2. 一个队列，存放「待扩展」的结点。
3. 
   
4. 一个访问标记，防止同一个结点被重复入队。
5. 
   
6. 可选的层数或距离数组。
7. 
   

框架如下：

// 适用于 C++17
#include <queue>
#include <vector>

void bfs(int start, const std::vector<std::vector<int>>& adj) {
std::vector<bool> visited(adj.size(), false);
std::queue<int> 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，每步可以上下左右移动一格，求最少步数并输出一条路径。

// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

struct Point {
int r;
int c;
};

int bfsMaze(const std::vector<std::vector<int>>& grid,
Point start, Point target,
std::vector<Point>& path) {
const int rows = static_cast<int>(grid.size());
const int cols = static_cast<int>(grid[0].size());

std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
std::vector<std::vector<Point>> parent(rows, std::vector<Point>(cols, {-1, -1}));

std::queue<Point> 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。因为队列的先进先出，距离相同的起点会一起扩展，第一次到达某个格子时的距离就是它到最近起点的距离。

// 适用于 C++17
std::vector<std::vector<int>> multiSourceBfs(
const std::vector<std::vector<int>>& grid,
const std::vector<Point>& sources) {
const int rows = static_cast<int>(grid.size());
const int cols = static_cast<int>(grid[0].size());
std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
std::queue<Point> 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 时放到队尾。这样队列仍然保持「距离非降」的顺序，第一次出队时的距离就是最短距离。

// 适用于 C++17
#include <deque>
#include <limits>

int zeroOneBfs(int start, int target,
const std::vector<std::vector<std::pair<int, int>>>& adj) {
const int n = static_cast<int>(adj.size());
const int INF = std::numeric_limits<int>::max();
std::vector<int> dist(n, INF);
std::deque<int> 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。

常见坑点

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. 用vector<bool>之外的结构存距离却忘记初始化

❌std::vector<std::vector<int>> dist(rows, std::vector<int>(cols));默认是 0，和「未访问」混淆。

✅ 初始化为 -1 或INF，与有效距离区分开。

8. 认为 BFS 能枚举所有路径

❌ 用 BFS 统计从起点到终点的所有路径条数，却只保留第一次访问。

✅ 枚举路径用 DFS 回溯；BFS 适合最短路和按层统计。

总结

BFS 的代码模板很短，真正决定正确性的是两个顺序：先判断边界再访问数组，先标记再入队。把这两个顺序写对，再根据边权选择普通队列、双端队列还是优先队列，绝大多数「最短步数」类问题都能套用同一套框架。