标准bfs遍历图需用std::queue存待访问节点、std::vector作visited标记；入队前必须检查并更新visited，避免重复入队；邻接表用std::vector，多源起点可一并入队；最短路径长度即层数，终点pop时返回距离。
怎么用 std::queue 写标准 BFS 遍历图
核心就是用 std::queue 存待访问节点，配合 std::vector<bool></bool> 或 std::unordered_set 做访问标记。别手写队列，std::queue 足够快且安全。
常见错误：入队前不检查是否已访问，导致重复入队、死循环或结果错乱；或者把邻接点直接 push 进队却忘了更新 visited 标记。
- 图用邻接表存：
std::vector<:vector>></:vector>，索引是节点编号 - 初始化时把起点 push 进
std::queue，并设visited[start] = true - 每次 pop 一个节点，遍历其所有邻接点；对每个未访问的邻接点，先标
visited[nbr] = true，再 push - 如果要记录层数（比如最短距离），用额外变量
level_size控制每层边界，或在队列中存std::pair<int int></int>（节点+深度）
遇到环或无向图时怎么避免重复访问
无向图边是双向的，0→1 和 1→0 都存在，不加访问控制会反复横跳。BFS 本身不解决环，靠 visited 数组硬拦。
容易踩的坑：用 std::set 或 std::map 当 visited 容器——虽然能用，但比 std::vector<bool></bool> 慢 3–5 倍（尤其节点数大时）。节点编号连续就用 vector；编号稀疏才考虑 std::unordered_set<int></int>。
立即学习“C++免费学习笔记（深入）”；
- 初始化
visited大小要 ≥ 最大可能节点编号 + 1（别只按边数算） - 如果输入节点编号从 1 开始，vector 下标 0 就别浪费，直接开
visited[n + 1]，用 1~n - 多源 BFS（如多个起点同时开始）？一起 push 到 queue 开头，并统一设对应 visited 为 true
怎么用 BFS 找无权图最短路径长度
BFS 天然按层扩展，第一次访问到终点时的层数就是最短距离。不需要 relax 操作，也不用优先队列。
关键点在于「何时返回」：不是一看到终点就 return，而是等它从 queue pop 出来那一刻才算真正到达——因为只有 pop 才代表该节点被正式处理。
- 用
int dist记录当前层深度，每处理完一层（即 queue 中上层所有节点）就dist++ - 更稳妥的做法是队列存
std::pair<int int></int>：{node, distance}，遇到终点直接返回distance - 如果终点不可达，循环结束没返回，记得补
return -1或抛异常，别让函数静默退出 - 注意：这个“最短路径长度”指边数，不是权重和；有权图必须换 Dijkstra 或 0-1 BFS
LeetCode 例题 199. Binary Tree Right Side View 怎么套 BFS
本质是取每层最后一个节点，不是传统图 BFS，但共享同一套 queue + level size 模式。
别用递归或 DFS 模拟层序——容易绕晕。就用 BFS，每层遍历完，把最后一个元素加入结果即可。
- 用
int level_size = q.size()锁定当前层节点数 - for 循环
level_size次，每次 pop；第level_size次 pop 的节点就是右视图要的那个 - 不需要额外存整层节点，空间 O(w)，w 是最大层宽，比存 vector
> 省得多 - TreeNode* 指针进 queue 没问题，但确保判空：
if (node->left) q.push(node->left)
BFS 看似简单，实际调试时 70% 的 bug 出在 visited 更新时机和 queue 入队条件上。写完务必用含自环、孤立点、单节点的 case 过一遍。
