图的广度优先搜索从起始顶点开始逐层遍历，使用队列和访问标记数组避免重复访问；C++中常用邻接表vector<vector<int>>结合queue实现，示例构建5个顶点的图并从0开始BFS，输出0 1 2 3 4；适用于最短路径、连通分量等场景，稀疏图推荐邻接表，可扩展parent数组记录路径。
图的广度优先搜索（BFS）是一种用于遍历或搜索图的算法，它从起始顶点开始，逐层访问其邻接节点，使用队列保证访问顺序。在C++中，可以通过邻接表或邻接矩阵结合标准库queue来高效实现。
图的表示方式：邻接表
通常使用vector<vector<int>>表示邻接表，每个索引对应一个顶点，存储与其相连的顶点列表。
假设有5个顶点，边为 (0,1), (0,2), (1,3), (1,4)，邻接表构造如下：
vector<vector<int>> graph(5);
graph[0] = {1, 2};
graph[1] = {3, 4};
// 其他默认为空
BFS核心逻辑与实现步骤
BFS的关键是使用队列和访问标记数组，避免重复访问节点。
立即学习“C++免费学习笔记（深入）”；
步骤说明：
- 创建布尔数组
visited记录每个顶点是否已访问 - 创建队列，将起始顶点入队并标记为已访问
- 当队列非空时，取出队首顶点并访问
- 将其所有未访问的邻接顶点入队并标记
- 循环直到队列为空
C++实现代码：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(const vector<vector<int>>& graph, int start) {
int n = graph.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 : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
完整可运行示例
以下是一个完整的程序，构建图并执行BFS：
int main() {
vector<vector<int>> graph(5);
graph[0] = {1, 2};
graph[1] = {0, 3, 4};
graph[2] = {0};
graph[3] = {1};
graph[4] = {1};
cout << "BFS traversal: ";
bfs(graph, 0);
return 0;
}
输出：
0 1 2 3 4
注意事项与优化建议
BFS适用于无权图的最短路径问题，也可扩展用于层级遍历、连通分量判断等场景。
- 确保图的顶点编号从0开始连续，否则需用map管理visited状态
- 若需记录路径，可额外维护
parent数组，在入队时记录前驱节点 - 对于稀疏图，邻接表比邻接矩阵更节省空间
- 注意处理孤立节点或非连通图的情况，可能需要多次调用BFS
