c++中如何实现图的广度优先遍历_c++图BFS遍历方法

答案：C++中BFS通过队列实现逐层遍历，使用邻接表存储图并用visited数组标记节点，从起始点入队开始，循环出队并访问其未标记的邻接点，直至队列为空，确保每个节点仅处理一次，时间复杂度为O(V+E)。

在C++中实现图的广度优先遍历（BFS），核心是使用队列结构来逐层访问图中的节点。BFS适用于无向图或有向图，常用于寻找最短路径、连通性判断等场景。

图的存储方式：邻接表

通常用邻接表表示图，便于遍历每个节点的邻居。可以使用vector<vector<int>>来实现。

例如，graph[u] 存储所有与节点 u 相连的节点。

实现步骤说明

BFS的关键在于从起始节点出发，逐层扩展，避免重复访问。需要一个队列和一个标记数组。

立即学习“C++免费学习笔记（深入）”；

UP简历

基于AI技术的免费在线简历制作工具

72

查看详情

• 创建一个布尔数组 visited，记录节点是否被访问过
• 使用 queue<int> 存储待访问的节点
• 将起始节点入队，并标记为已访问
• 当队列不为空时，取出队首节点，访问其所有未访问的邻接点并入队

代码示例

以下是一个完整的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);
}
}
}
}
int main() {
int n = 5;
vector<vector<int>> graph(n);
// 构建无向图：0-1, 0-2, 1-3, 2-4
graph[0] = {1, 2};
graph[1] = {0, 3};
graph[2] = {0, 4};
graph[3] = {1};
graph[4] = {2};
cout << "BFS traversal: ";
bfs(graph, 0);
cout << endl;
return 0;
}

注意事项

BFS确保每个节点只被处理一次，时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。

• 记得初始化 visited 数组，防止重复访问
• 对于非连通图，可能需要对每个未访问节点调用 BFS
• 如果图是用邻接矩阵存储的，遍历邻接点的方式要改为循环检查 matrix[u][v]

基本上就这些。只要掌握队列和访问标记的配合，BFS就不难实现。