广度优先搜索从起始节点开始逐层遍历，使用队列和访问标记数组实现，适用于求解最短路径、连通分量等问题，时间复杂度O(V+E)，空间复杂度O(V)。
广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图的算法，它从起始顶点开始，逐层访问其邻接顶点，直到访问完所有可达顶点。在C++中，通常使用队列和访问标记数组来实现BFS。
图的表示方式
在C++中，图常用邻接表或邻接矩阵表示。对于稀疏图，邻接表更节省空间且效率更高。
使用vector<vector<int>>可以方便地实现邻接表：
// 假设n为顶点数
vector<vector<int>> graph(n + 1); // 若顶点从1开始编号
// 添加边 u -> v
graph[u].push_back(v);
graph[v].push_back(u); // 无向图需双向添加
BFS核心实现步骤
BFS借助queue保证按层次顺序访问节点，同时用布尔数组记录访问状态，防止重复访问。
立即学习“C++免费学习笔记（深入）”；
基本流程如下：
- 从起始节点开始，标记为已访问，并入队
- 当队列非空时，取出队首节点并访问
- 将其所有未访问的邻接节点标记并入队
- 重复直到队列为空
示例代码：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(const vector<vector<int>>& graph, int start, int n) {
vector<bool> visited(n + 1, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " "; <font color="#008000">// 访问当前节点</font>
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
完整可运行示例
以下是一个构建无向图并执行BFS的完整程序：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n = 5; <font color="#008000">// 5个顶点</font>
vector<vector<int>> graph(n + 1);
<font color="#008000">// 添加边</font>
graph[1].push_back(2); graph[2].push_back(1);
graph[1].push_back(3); graph[3].push_back(1);
graph[2].push_back(4); graph[4].push_back(2);
graph[3].push_back(5); graph[5].push_back(3);
cout << "BFS traversal: ";
bfs(graph, 1, n);
return 0;
}
输出结果为：1 2 3 4 5，体现了逐层遍历的特点。
应用场景与注意事项
BFS常用于求解无权图的最短路径、连通分量、拓扑排序等问题。注意以下几点：
- 确保图的顶点编号与数组大小匹配
- 有向图只需单向添加边
- 若图不连通，需对每个未访问节点调用BFS以遍历全部连通块
- 队列操作时间复杂度为O(V + E)，空间复杂度为O(V)
