标准BFS用std::queue管理待访节点、std::vector记录访问状态；需在入队时立即标记“已入队”，避免重复入队；邻接表为vector，起始节点入队前即设visited[start]=true。
用 std::queue 和 std::vector 实现标准 BFS 遍历
广度优先搜索在 C++ 中最常用、最稳妥的实现方式是配合 std::queue 管理待访问节点，用 std::vector<bool></bool> 或 std::vector<int></int> 记录访问状态。不推荐手写队列或用 std::stack 替代——后者会变成 DFS。
常见错误是把邻接点直接压入队列却不标记已入队，导致重复入队甚至死循环。正确做法是：**发现未访问邻居时，立即标记为“已入队”（而非“已访问”），再入队**。
- 图用邻接表表示：
vector<vector>></vector>，索引为节点编号 - 访问数组建议用
vector<bool></bool>，空间省；但注意它不是标准容器，不能取地址，若需调试可临时换vector<int></int> - 起始节点入队前就要设
visited[start] = true
void bfs(const vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), 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);
}
}
}
}
如何用 BFS 求无权图的最短路径长度
BFS 天然适合求无权图中从起点到各点的最短路径（边数最少）。只需把队列换成 queue<pair int>></pair>，存 {节点, 距离}，或单独用 vector<int></int> 记录 dist[v]。
容易忽略的点：起点距离是 0，不是 1；更新邻居距离时，必须是 dist[u] + 1，且仅当 dist[v] == -1（未访问）才赋值。
立即学习“C++免费学习笔记（深入）”；
- 初始化
dist全为-1，代表不可达 - 每次从队列弹出节点
u后，对每个未访问邻居v执行dist[v] = dist[u] + 1 - 若只关心某终点，可在设置
dist[v]后立刻检查是否等于目标，提前返回
遇到环或非连通图时怎么避免漏节点
BFS 本身不会因环崩溃，但单次调用只能遍历一个连通分量。如果图可能不连通（比如输入是森林），必须在外层加循环扫描所有节点，对每个 !visited[i] 启动一次 BFS。
典型错误是只从 0 开始搜，结果 100 个节点只输出了前 20 个——其余节点根本没被检查。
- 不要假设节点编号连续或从 0 开始；若输入含离散编号（如 {2,5,9}），先映射到 0..n-1，或改用
unordered_map存visited - 若图用邻接矩阵（
vector<vector>></vector>），空间复杂度 O(V²)，V > 1e4 就容易 MLE，此时必须切回邻接表 - 多源 BFS（如多个起点同时开始）只需初始把所有起点压入队列，并设对应
dist为 0
为什么不用 std::deque 或自己写队列
std::queue 默认基于 std::deque，已经足够高效；手动换成 std::deque 并不会提速，反而增加理解成本。真正影响性能的是图的存储结构和内存局部性。
更大的陷阱在于：有人用 vector 模拟队列（pop_front() 是 O(n)），导致 BFS 退化成 O(V·E) —— 这比算法本身还慢。
- 确认你用的是
#include <queue></queue>，不是<vector></vector>加erase(begin()) - 若需频繁中间插入/删除，那不是 BFS 场景，该换算法
- 竞赛中若卡常，可尝试
ios_base::sync_with_stdio(false); cin.tie(nullptr);加速输入，而非折腾容器
边界情况比想象中多：空图、单点、自环边（u == v）、重边。写完先用这三组数据过一遍——很多 bug 都出在这里。
