BFS用std::queue和std::vector实现可保证首次访问即最短路径；需入队前更新dist和prev，用prev数组倒推路径；网格BFS需扩展状态维度，注意去重与越界检查。
用 std::queue 和 std::vector 实现 BFS 最短路径
广度优先搜索（BFS）天然适合无权图的最短路径问题，C++ 中不用手写队列，直接用 std::queue 配合 std::vector 存邻接表或距离数组即可。关键不是“能不能搜到”，而是“怎么保证第一次到达就是最短”。BFS 按层扩展，所以只要某节点第一次被访问，当前步数就是它到起点的最短距离。
常见错误是：用 std::stack 或递归模拟 BFS；或者没做访问标记，导致重复入队、死循环；又或者把距离更新写在出队后而非入队时——这会导致同一节点被多次更新为更长路径。
- 初始化距离数组
dist为 -1（未访问），dist[start] = 0 - 入队前就设置
dist[next] = dist[curr] + 1，避免出队后再更新 - 邻接表建议用
vector<vector>></vector>，索引即节点编号，适合点数 ≤ 1e5 的常规场景 - 如果图含重边或自环，建图时可直接跳过（不影响最短路径），无需额外去重
如何还原最短路径（不只是长度）
只返回距离值不够，实际常需输出具体路径。这时不能只记距离，得记录每个节点的前驱（prev 数组）。BFS 过程中，一旦通过 curr 到达 next，就设 prev[next] = curr。注意：这个赋值必须发生在首次访问 next 时，且仅一次。
还原路径时从终点倒推，用 vector 收集再反转。别用递归回溯——可能栈溢出，也违背 BFS 的迭代本质。
立即学习“C++免费学习笔记（深入）”；
-
prev数组类型应为vector<int></int>，初值填 -1 表示无前驱 - 终点不可达时，
prev[end]仍为 -1，需提前检查 - 若需多条最短路径之一，当前方案够用；若要全部路径，BFS 不适用，得换 DP 或 DFS 剪枝
处理带障碍/条件的网格 BFS（如 LeetCode 505）
二维网格上的 BFS 是高频变体，节点是坐标对 (r, c)，常用 queue<pair>></pair> 或封装为结构体。难点不在搜索逻辑，而在状态定义和去重维度。
典型坑是：只用行列坐标去重，忽略其他状态（比如钥匙持有情况、剩余步数、方向等），导致漏解或错解。例如“迷宫中捡钥匙开门”，状态就得是 (r, c, keys_mask)，哈希或三维数组判重。
- 方向数组推荐写成
const vector<pair>> dirs = {{-1,0},{0,1},{1,0},{0,-1}};</pair> - 越界检查必须放在访问前：
r = rows || c = cols - 障碍格（如
'#'或1）应在入队前跳过，别让它进队再判断 - 用
vector<vector>></vector>判重时，确保维度与状态空间一致；否则改用set<tuple>></tuple>
性能敏感时要注意的细节
BFS 时间复杂度本是 O(V + E)，但 C++ 实现中几个小动作会悄悄拖慢速度：频繁调用 queue::empty()、反复构造临时 pair、用 map 替代 vector 存图、甚至调试时开着 std::endl 刷屏。
真正卡常的点往往藏在数据结构选择里。比如点编号稀疏（1, 100, 1000000），用 vector 就浪费内存；但若只是 1~N 连续编号，vector 的 cache 局部性远好于 map 或 unordered_map。
- 用
.emplace()替代.push()构造节点，避免拷贝 - 预分配
dist和prev数组大小，避免运行时扩容 - 若终点明确且图很大，找到终点立即
return，别坚持遍历全图 - 调试时禁用同步：加
ios::sync_with_stdio(false); cin.tie(nullptr);
最短路径本身不难，难的是根据输入形式快速决定状态粒度、判重方式和容器选型。边界稍一模糊，BFS 就退化成暴力枚举。
