std::queue 是 C++ 中实现 BFS 最常用方式，需配合访问标记数组避免重复入队，且标记必须在入队时设置；图可用邻接表或邻接矩阵表示，稀疏图推荐邻接表。
用 std::queue 实现标准 BFS 遍历
广度优先搜索在 C++ 中最常用、最直观的实现方式是借助 std::queue，配合访问标记数组（或 std::set/std::unordered_set）避免重复入队。核心逻辑是：从起点入队 → 循环取队首 → 访问所有未访问邻接点并入队。
关键点：
-
std::queue是 FIFO 容器适配器，不支持随机访问或遍历，但完全满足 BFS 层序需求 - 图可用邻接表（
vector<vector>></vector>）或邻接矩阵（vector<vector>></vector>）表示；稀疏图强烈推荐邻接表 - 访问标记必须在入队时设置（而非出队时），否则同一节点可能被多次加入队列
vector<vector<int>> graph = {{1,2}, {0,3}, {0,3}, {1,2}};
vector<bool> visited(graph.size(), false);
queue<int> q;
q.push(0);
visited[0] = 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);
}
}
}
处理带权图或需要记录距离时用 pair 或结构体
纯 BFS 仅适用于无权图或所有边权相等的情形。若需在 BFS 过程中同步维护节点距离（如求最短路径长度），常见做法是把 node 和 dist 绑定为 pair<int int></int> 入队。
注意：
立即学习“C++免费学习笔记（深入）”；
- 不要用
queue<int></int>配合外部数组“延迟更新”距离——这会导致距离值与实际出队顺序错位 - 如果边权不全为 1（比如有权重为 2 的边），BFS 不再适用，应改用 Dijkstra 算法
- 若图含负权边，Dijkstra 也不适用，需考虑 Bellman-Ford 或 SPFA
queue<pair<int, int>> q; // {node, dist}
q.push({0, 0});
vector<int> dist(graph.size(), -1); // -1 表示未访问
dist[0] = 0;
while (!q.empty()) {
auto [u, d] = q.front(); q.pop();
for (int v : graph[u]) {
if (dist[v] == -1) {
dist[v] = d + 1;
q.push({v, d + 1});
}
}
}
多源 BFS：多个起点同时入队
当问题要求“从任意一个起点出发的最短距离”（如矩阵中多个 '0' 扩散到 '1'），可将所有起点一次性压入队列，并初始化对应距离为 0。这本质上仍是标准 BFS，只是初始队列非单元素。
典型场景包括：
- 01 矩阵中每个位置到最近 0 的距离
- 腐烂橘子传播时间
- 双向 BFS 的前半部分初始化
陷阱：
- 误写成循环中逐个 push 再单独处理——这样会破坏层序性，必须所有起点先入队、再统一开始 while 循环
- 忘记对多个起点也做访问标记，导致重复入队
避免常见内存与逻辑错误
BFS 在 C++ 中容易因容器误用或边界疏忽引发崩溃或死循环：
- 图节点编号从 0 开始，但
graph.size()可能小于最大节点 ID —— 若输入含孤立大编号点（如节点 100 但只有 5 条边），需用max_node_id + 1初始化visited或dist -
queue::front()和queue::pop()是两个独立操作，不能省略pop()，否则无限循环 - 使用
vector<vector>></vector>存图时，确保每行都已resize或用push_back正确构建，空行会导致范围访问越界 - 在类成员函数中复用
queue时，记得每次调用前queue = queue<int>()</int>清空（C++11 后可直接赋值空队列）
图论 BFS 看似简单，真正难的是根据题意准确建模——节点定义、边是否存在、是否允许回头、距离含义是否随层变化，这些细节一旦错，整个 BFS 就偏离目标。
