BFS中访问标记必须在入队时设置，否则同一节点可能被多次入队；邻接表优于邻接矩阵（尤其稀疏图）；网格BFS需手动处理边界与障碍；距离应随节点入队时一并记录。
用 std::queue 实现 BFS 时，访问标记必须在入队时设置
这是最容易出错的点：很多人习惯在 q.pop() 后才设 visited[u] = true，结果导致同一节点被多次入队——尤其在稀疏图或网格中，会显著拖慢速度，甚至爆内存。
- 原因：队列里可能同时存在多个指向同一节点的副本，比如从不同路径抵达同一个
v，若没提前标记，它们都会被压入队列 - 正确做法：每次调用
q.push(v)前，立刻执行visited[v] = true - 不推荐用
std::set或std::unordered_set替代布尔数组——除非节点编号极大或不连续；数组访问是 O(1) 且无哈希开销
邻接表 vs 邻接矩阵：选错结构会让 BFS 变慢一倍以上
对大多数图问题（尤其是稀疏图），vector<vector>></vector> 是更优选择；邻接矩阵 vector<vector>></vector> 在边数远小于 n² 时纯属浪费空间和遍历时间。
- 邻接表：遍历每个节点只需检查其真实邻居，总时间复杂度为 O(V + E)
- 邻接矩阵：每次都要扫完整行（n 次），哪怕该节点只连 1 条边，总时间变成 O(V²)
- 典型误用场景：用矩阵存一个 1000 节点、平均度数为 3 的社交关系图——99.7% 的矩阵元素是 false，却要反复判断
网格类 BFS 必须手动处理边界和障碍，不能依赖图结构自动过滤
二维网格不是天然的图对象，graph[x][y] 这种写法不存在；你得自己算四个方向坐标，并显式检查是否越界、是否可通行。
- 常见错误：直接用
if (grid[nx][ny] == 0)判断，但没先验证nx和ny是否在[0, n)和[0, m)范围内，导致越界读取 - 建议把方向偏移封装成
vector<pair>></pair>，比如{{-1,0},{0,1},{1,0},{0,-1}}，避免手写四次重复逻辑 - 如果障碍是字符（如
'#'）或状态位（如已访问标记复用原数组），注意别把标记逻辑和通行判断混在一起
需要记录距离时，别用外部数组“延迟更新”，要用 queue<pair>></pair>
有人想省事，只维护一个 dist[] 数组，在出队时再更新：dist[v] = dist[u] + 1。这会导致距离值与实际 BFS 层级错位——因为 u 出队顺序 ≠ 入队顺序，而 BFS 的最短性依赖于首次抵达即是最短。
立即学习“C++免费学习笔记（深入）”；
- 正确方式：把节点和当前距离打包入队，如
q.push({v, d + 1})，确保每个节点携带它被发现时的真实距离 - 初始化时所有
dist[i]设为 -1（未访问），仅在入队时赋值，出队时不改 - 多源 BFS（如多个起点同时扩散）也适用同一模式：所有起点
{start_i, 0}一次性入队，后续逻辑完全不变
