C++中BFS使用队列按层遍历，以邻接表存储图，用visited数组防重访；对非连通图需遍历所有节点启动多次BFS；可扩展用于无权图最短路径、二分图判定等。
用C++实现图的广度优先搜索（BFS），核心是借助队列（queue）按层扩展访问节点，并用数组或集合标记已访问节点，避免重复入队。
使用邻接表存储图
邻接表适合稀疏图，用 vector<vector>></vector> 表示：下标为起点，内部 vector 存所有邻接点。
例如：边 (0→1), (0→2), (1→3)，对应 graph[0] = {1,2}，graph[1] = {3}。
标准 BFS 实现（无权图，从起点开始遍历）
以下代码输出 BFS 遍历顺序（也可改造成求最短距离、连通分量等）：
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
void bfs(const vector<vector<int>>& graph, int start) {
int n = graph.size();
vector<bool> visited(n, false);
queue<int> q;
visited[start] = true;
q.push(start);
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);
}
}
}
cout << endl;
}
// 示例用法
int main() {
// 构建 4 个节点的有向图：0→1, 0→2, 1→3, 2→3
vector<vector<int>> graph(4);
graph[0] = {1, 2};
graph[1] = {3};
graph[2] = {3};
// graph[3] 为空
bfs(graph, 0); // 输出：0 1 2 3
return 0;
}
扩展：支持无向图与多连通分量
若图不连通，需对每个未访问节点启动一次 BFS：
- 外层加循环遍历所有节点
i ∈ [0, n) - 每次遇到
!visited[i]就调用一次 BFS，可视为发现一个新连通分量 - 无向图建图时，边
u-v要双向添加：graph[u].push_back(v); graph[v].push_back(u);
常见变体用途
-
单源最短路径（无权图）：用
vector<int> dist(n, -1)</int>记录距离，起始点dist[start] = 0，每次入队时设dist[v] = dist[u] + 1 - 判断二分图：用颜色数组（如 0/1），BFS 过程中检查邻接点是否冲突
-
层序遍历控制：用额外变量记录当前层节点数（如先记
int levelSize = q.size()），每轮处理完一层再继续
基本上就这些。BFS 关键在于“先进先出”和“即时标记”，别漏判 visited 就不会死循环。
