最稳妥的C++ BFS实现是用std::queue管理节点、std::vector记录访问状态；必须“入队即标记”，邻接表按图类型双向/单向建边，路径还原需维护parent数组并正确初始化与回溯。
用 std::queue 和 std::vector 实现标准 BFS 遍历
广度优先搜索在 C++ 中最稳妥的实现方式是依赖 STL 容器：用 std::queue 管理待访问节点，用 std::vector<bool></bool> 或 std::vector<int></int> 记录访问状态或距离。别手写队列，也别用 std::stack 混淆——BFS 的层序特性完全依赖 FIFO 行为。
常见错误是把邻接点一股脑 push 进队列却不标记已入队，导致重复入队、内存爆掉或死循环。正确做法是「入队即标记」，不是「出队才标记」。
- 初始化时将起点入队，并设
visited[start] = true - 每次从队首取节点
u，遍历其所有邻接点v - 对每个未访问过的
v，立刻设visited[v] = true，再 push 入队 - 若需记录路径长度，用
dist[v] = dist[u] + 1；若需还原路径，额外维护parent[v] = u
邻接表建图时注意边方向与重边处理
图的存储方式直接影响 BFS 正确性。无向图要双向加边：adj[u].push_back(v) 和 adj[v].push_back(u) 缺一不可；有向图只加单向边。如果输入含重边（相同 u→v 多次），std::vector 邻接表会存多份，但只要访问标记到位，不影响结果——只是略微拖慢常数。
别用邻接矩阵存稀疏图：10⁵ 节点时 int adj[100000][100000] 直接编译失败或 OOM。真要动态建图，用 vector<vector>></vector> 即可，空间复杂度 O(V+E)。
立即学习“C++免费学习笔记（深入）”；
- 输入 N 个节点（编号 0~N-1）和 M 条边，先
vector<vector>> adj(N)</vector> - 读入每条边后，按图类型决定是否双向插入
- 若题目说「可能有自环」，检查
u == v，通常跳过（避免自己访问自己）
从 BFS 到最短路径：如何还原具体路径
BFS 本身只保证首次到达某点时路径最短（无权图），但默认不保存路径细节。要输出从起点到终点的完整节点序列，必须在搜索时记录每个节点的前驱 parent[v]。终点回溯到起点后，再反转数组即可。
容易忽略的是：起点的 parent[start] 应设为 -1 或特殊值，否则回溯时无法终止；另外，若终点根本不可达，parent[end] 保持初始值（如 -1），需提前判断，否则反转空路径会 crash。
- 声明
vector<int> parent(n, -1)</int>，起点处parent[start] = -2或保留 -1 并单独标记 - 当从
u扩展到v时，执行parent[v] = u - 回溯时用
while (v != -1) { path.push_back(v); v = parent[v]; }，最后reverse(path.begin(), path.end())
遇到超时或 WA？检查这三处硬伤
练习中 80% 的 WA 或 TLE 来自边界疏漏，而非算法逻辑。尤其注意：节点编号是否从 0 开始？输入的边是否包含无效索引（如 N=5 却出现节点 6）？队列是否用了 int 而非 size_t 导致下标越界？
- 读入节点数 N 后，邻接表大小必须是
adj.resize(N)，不是N+1（除非题目明确编号 1~N 且你习惯偏移） -
queue存的是节点编号，不是指针或结构体——别为了“省事”塞pair<int></int>却忘了更新逻辑 - 多组测试用例时，每次都要清空
adj、重置visited和parent，不能只memset部分内存
路径查找类题目的关键不在 BFS 框架，而在建图与回溯的衔接是否干净。一个没初始化的 parent 数组，比算法写错更难调试。
