用 std::queue 实现 BFS 最稳，因其底层基于 std::deque 或 std::list 保证 O(1) 入队出队，避免 vector 模拟时 erase 头部导致 O(n) 复杂度；需独立初始化 visited 数组并入队前标记，邻接表优先用 vector 而非 map 以提升缓存效率；节点规模适配 n ≤ 1e5、m ≤ 2e5；路径还原应使用 parent 数组而非字符串拼接。
用 std::queue 实现 BFS 最稳，别手写队列
标准库的 std::queue 是 BFS 的天然搭档，底层用 std::deque（默认）或 std::list 都能保证 O(1) 入队出队。自己用 vector 模拟队列容易在 pop 时误删头元素导致 O(n) 复杂度，一跑稀疏图就卡顿。
常见错误现象：vector.erase(vector.begin()) 反复调用；或者用 vector[0] 取头但忘了 erase 后索引全偏移。
- 初始化：用
std::queue<int></int>存节点编号，配合邻接表vector<vector>></vector> - 访问标记必须独立于队列——用
vector<bool> visited(n, false)</bool>，别靠队列是否为空判断“是否处理过” - 入队前立刻设
visited[u] = true，否则同一节点可能被多次加入（尤其无向图）
邻接表存图时，vector<vector>></vector> 比 map<int vector>></int> 快得多
除非节点编号稀疏且跨度极大（比如只有 1 和 1e9 两个点），否则用哈希表存邻接关系纯属拖慢 BFS。下标访问是连续内存，vector<vector>></vector> 的 cache 局部性好，遍历邻居时 CPU 预取有效。
使用场景：节点数 n ≤ 1e5，边数 m ≤ 2e5 —— 这是典型竞赛/工程图规模。
立即学习“C++免费学习笔记（深入）”；
- 建图：对每条边
u → v，执行graph[u].push_back(v)；无向图则再加graph[v].push_back(u) - 注意：节点编号通常从 0 或 1 开始，初始化
graph大小别写错，比如vector<vector>> graph(n + 1)</vector> - 如果输入含重边，BFS 本身不敏感，但
visited能自然去重；若需严格去重建图，可先用set收集再转vector，但一般没必要
visited 数组漏初始化或大小不对，直接导致无限循环或越界
这是最常打断调试的硬伤。BFS 一旦把未标记的节点反复压入队列，程序要么 SIGSEGV（访问非法内存），要么死循环（队列永远不空）。
错误信息示例：vector::_M_range_check: __n (which is 123456789) >= this->size() (which is 1000)，或程序卡住不动、CPU 占满。
- 务必在 BFS 前完成初始化：
vector<bool> visited(n, false)</bool>，其中n是最大可能节点编号 + 1 - 如果图节点编号不连续（如只给了 500 个点，编号是随机的 1000~1999），得先离散化，或改用
unordered_map<int bool></int>，但性能下降明显 - 别用
int visited[N]这种静态数组——N 写小了越界，写大了栈溢出（尤其递归+大数组混用时）
需要路径还原？别在 BFS 里拼字符串，存 parent 数组最轻量
BFS 本身不记录路径，但多数实际需求（比如找最短路、输出方案）都需要回溯。拼接字符串或 vector 在每次入队时拷贝，时间空间双爆炸。
性能影响：字符串拼接平均 O(L)（L 是路径长度），总复杂度退化到 O(n²)；而 parent 数组只需 O(1) 写 + O(L) 回溯。
- 声明：
vector<int> parent(n, -1)</int>，初始节点的parent[start] = start或保持 -1 - 当从
u扩展到v时，写parent[v] = u，仅此一句 - 还原路径：用 while 循环从终点往回跳
parent，用stack<int></int>或逆序 vector 收集，避免递归栈深问题
