根本原因是未在入队前检查访问状态，BFS必须“入队即标记”，否则同一节点可能被多次加入队列，导致queue膨胀、卡死或结果错乱；邻接表更适合稀疏图，邻接矩阵仅适用于极小稠密图。
用 std::queue 实现 BFS 时，为什么节点老是重复访问？
根本原因是没在入队前检查是否已访问过，或者把访问标记写在了出队之后。BFS 要求「入队即标记」，否则同一节点可能被多次加入队列。
常见错误现象：std::queue 越来越大、程序卡死、结果重复或错乱；调试时发现某个 node 被压入队列两三次。
- 入队前必须查
visited[node]，为false才入队 + 立即设为true - 不要等
queue.front()出队后再标记——这时邻居可能已被重复加入 - 图用邻接表时，确保遍历的是
graph[node]而非graph[i]（下标错位）
邻接矩阵 vs 邻接表：选哪个影响 BFS 性能？
邻接矩阵查边是 O(1)，但遍历所有邻居是 O(V)；邻接表遍历邻居是 O(degree(node))，总时间更接近 O(V + E)。
使用场景：稀疏图（比如树、网格、社交关系）一律用邻接表；只有极小且稠密的图（V ）才考虑邻接矩阵。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 邻接表推荐用
vector<vector>></vector>或vector<unordered_set>></unordered_set>，避免重复边干扰 - 邻接矩阵用
vector<vector>></vector>，初始化注意全false，别漏掉对角线（除非允许自环） - 如果边权非 0/1，BFS 不适用——该换 Dijkstra 或 0-1 BFS
std::queue 里该存什么？指针、索引还是结构体？
99% 的情况存索引（int）最安全。存指针容易悬空，存结构体增大拷贝开销，尤其含 std::string 或容器时。
使用场景：网格搜索存 pair<int int></int> 可以，但要用 queue<pair int>></pair> 显式声明；带步数的 BFS 建议封装成结构体，但字段要轻量（如两个 int + 一个 short）。
- 别用
queue<node></node>，除非你严格控制Node生命周期且不 delete - 避免在循环里反复构造临时对象入队，比如
q.push({x, y, step+1})比q.push(Node{x,y,step+1})更稳（后者依赖构造函数无异常） - 如果需要路径回溯，单独用
vector<int> parent</int>记录前驱，别塞进队列
从二维网格启动 BFS，边界检查总出错怎么办？
典型错误是把 x >= 0 && x = 0 && y 写成 <code>&& y 这类低级笔误，或漏判 <code>grid[x][y] == 0（障碍物）。
性能影响：少一次判断可能让非法坐标访问 grid 引发越界崩溃，或逻辑上走入死路。
- 把边界检查抽成 inline 函数，比如
auto valid = [&](int x, int y) { return x >= 0 && x = 0 && y - 四个方向用数组写死：
const vector<pair int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};</pair>，别手写四次 if - 起点入队前也必须调用 valid()，别假设输入一定合法
