bfs通过队列实现逐层遍历，先访问起始节点并标记，再将其未访问的邻接节点入队，重复直至队列为空；示例代码展示了无向图和网格中最短路径的应用，适用于最短路径、连通分量、状态搜索等问题。
广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图或树的算法。它从起始节点开始，逐层访问其邻居节点，直到找到目标节点或遍历完整个图。C++ 中实现 BFS 通常借助队列（queue）结构来保证先进先出的访问顺序。
基本思路与实现步骤
BFS 的核心思想是：从源点出发，先访问所有直接相邻的节点，再依次访问这些相邻节点的未访问邻居，依此类推，像水波一样层层扩散。
实现流程如下：
- 使用一个队列存储待访问的节点
- 使用一个布尔数组或集合记录已访问的节点，防止重复访问
- 将起始节点入队，并标记为已访问
- 当队列非空时，取出队首节点，访问其所有未访问的邻接节点并入队
- 重复上述过程直到队列为空
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(const vector<vector<int>>& adj, int start) {
int n = adj.size();
vector<bool> visited(n, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " "; // 输出当前访问的节点
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
int main() {
// 构建一个简单的无向图：0-1, 0-2, 1-3, 2-4
vector<vector<int>> adj(5);
adj[0] = {1, 2};
adj[1] = {0, 3};
adj[2] = {0, 4};
adj[3] = {1};
adj[4] = {2};
cout << "BFS 遍历结果: ";
bfs(adj, 0); // 从节点 0 开始遍历
cout << endl;
return 0;
}
在网格中的 BFS 应用
BFS 常用于二维网格问题，比如迷宫最短路径、图像填充、岛屿问题等。此时节点是坐标 (x, y)，邻居是上下左右四个方向。
立即学习“C++免费学习笔记（深入）”；
示例：在 0-1 网格中求从左上角到右下角的最短路径（只能走 0）。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
if (grid[0][0] == 1) return -1;
int n = grid.size();
vector<vector<bool>> visited(n, vector<bool>(n, false));
queue<vector<int>> q;
q.push({0, 0, 1}); // {x, y, distance}
visited[0][0] = true;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
while (!q.empty()) {
auto cell = q.front(); q.pop();
int x = cell[0], y = cell[1], dist = cell[2];
if (x == n-1 && y == n-1) return dist;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n
&& !visited[nx][ny] && grid[nx][ny] == 0) {
visited[nx][ny] = true;
q.push({nx, ny, dist + 1});
}
}
}
return -1; // 无法到达终点
}
BFS 的典型应用场景
BFS 不仅用于图遍历，还在多种实际问题中有广泛应用：
- 最短路径问题：在无权图或网格中，BFS 能找到起点到终点的最少边数路径
- 连通分量检测：通过多次 BFS 可找出图中所有连通块
- 拓扑排序辅助：结合入度的 BFS 可实现 Kahn 算法
- 状态空间搜索：如八数码问题、单词接龙等，每个状态是一个节点
- 二叉树层序遍历：本质就是 BFS，按层输出节点值
基本上就这些。BFS 实现不复杂但容易忽略细节，比如访问标记的时机、边界判断、初始条件等。掌握好队列和状态管理，就能灵活应对各种变体问题。
