推荐使用 std::queue 而非 std::vector 模拟队列，因为 std::queue 底层默认采用 std::deque，支持均摊 o(1) 的 push 和 pop 操作；而 vector 头删需 erase(begin())，时间复杂度为 o(n)，在 bfs 中易导致性能退化。
为什么用 std::queue 而不是 std::vector 模拟队列
因为 BFS 本质依赖“先进先出”顺序，手动用 vector 的 erase(begin()) 或 pop_front()（需 deque）会引入 O(n) 删除开销，而 std::queue 底层默认用 std::deque，push() 和 front()/pop() 都是均摊 O(1)。用 vector + erase 在稠密图上可能让 BFS 退化成 O(V²)。
实操建议：
- 直接声明
std::queue<int> q;</int>，别自己写循环删首元素 - 如果需要访问队列长度或判空，用
q.size()和q.empty()，不要用q.size() == 0判空（语义不清） - 避免把
std::queue当容器遍历——它不支持迭代器，真要调试可临时拷贝到std::vector
邻接表怎么存才能快速获取邻居且不重复建边
用 vector<vector>></vector> 最直接：索引是顶点编号，内层 vector 存所有邻接点。但要注意方向——无向图必须双向加边，有向图只加单向；否则 BFS 会漏节点或走错方向。
常见错误现象：
- 从节点 0 出发没走到节点 2，打印邻接表发现
adj[0]里没有 2，但手动画图明明相连 → 忘了加反向边（无向图场景） - 构建时用
adj[u].push_back(v)却漏了v对应的adj[v].push_back(u) - 顶点编号从 1 开始，但
adj只开了n大小（下标 0 ~ n-1），导致访问adj[n]越界
正确初始化示例：vector<vector>> adj(n + 1);</vector>（n 为最大顶点编号，留足 1-based 空间）
如何在 BFS 中同步记录最短路径而非仅判断可达
只用一个 vector<int> dist</int> 只能知道距离，要还原路径就得回溯。标准做法是额外维护 vector<int> prev</int>，记录每个节点的前驱（即 BFS 中首次访问它时来自哪个节点）。终点往回跳 prev 直到 -1 或起点，再反转就是最短路径。
关键细节：
-
prev初始化为 -1（表示未访问），起点的prev[start] = -1或保持 -1，别设成自身 - 更新条件必须是「首次到达」：只有当
dist[next] == -1（或INT_MAX）时才更新dist[next]和prev[next] - 路径重建时用
vector收集再reverse()，别在 BFS 循环里拼字符串——性能差且难调试
示例片段：if (dist[next] == -1) { dist[next] = dist[cur] + 1; prev[next] = cur; q.push(next); }
遇到负权边或非单位边权还能用这个 BFS 吗
不能。这个实现隐含假设所有边权为 1（或等价于 1），所以层数 = 距离。一旦出现边权为 2、0 或 -1，BFS 的层级性就失效——更短的物理路径可能被更晚发现。
此时必须换算法：
- 非负边权 → 用 Dijkstra，配合
priority_queue - 含负权但无负环 → 用 Bellman-Ford 或 SPFA
- 边权全为 1 或 0 → 可用 0-1 BFS（双端队列），比 Dijkstra 更快
最容易被忽略的一点：很多人把带权图强行套用 BFS，跑出来路径“看起来对”，但只要存在一条边权为 2 的捷径，结果就不可靠——BFS 不会回头重算，它只认第一次到达的顺序。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
