答案：C++中BFS通过队列实现逐层遍历，使用邻接表存储图并用visited数组标记节点，从起始点入队开始，循环出队并访问其未标记的邻接点，直至队列为空，确保每个节点仅处理一次，时间复杂度为O(V+E)。
在C++中实现图的广度优先遍历（BFS），核心是使用队列结构来逐层访问图中的节点。BFS适用于无向图或有向图，常用于寻找最短路径、连通性判断等场景。
图的存储方式：邻接表
通常用邻接表表示图，便于遍历每个节点的邻居。可以使用vector<vector<int>>来实现。
例如，graph[u] 存储所有与节点 u 相连的节点。
实现步骤说明
BFS的关键在于从起始节点出发，逐层扩展，避免重复访问。需要一个队列和一个标记数组。
立即学习“C++免费学习笔记（深入）”；
- 创建一个布尔数组 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就不难实现。
评论（已关闭）
评论已关闭