如何通过BFS算法实现广度优先搜索并编写实战代码？

本文共计1209个文字，预计阅读时间需要5分钟。

标准库中的 `std::queue` 是最稳妥的选择，其底层默认使用 `std::deque`，支持 O(1) 的入队和出队操作，且无需手动管理内存。如果自己使用数组或链表模拟队列，容易在边界操作（如 front()）出错，还可能因不清除空队列而导致后续测试失败。

常见错误现象：std::queue::front() 或 pop() 在空队列上调用 → 未定义行为，Debug 模式下可能断言失败，Release 下直接读垃圾内存。

• 初始化时用 std::queue<:pair int>></:pair> 存坐标，比存指针或自定义结构体更轻量
• 进队前必须检查越界和访问合法性（比如是否是障碍、是否已访问过），否则重复入队拖慢速度甚至死循环
• 标记已访问的位置建议用独立的 std::vector<:vector>></:vector>，别依赖节点状态字段——BFS 中节点只进队一次，但状态字段若被多处修改，逻辑容易混乱

邻接点遍历顺序影响结果，但不影响连通性判断

BFS 本身不保证“字典序”或“顺时针”出队，只是按入队时间先后处理。如果你在网格中上下左右四个方向扩展，顺序写成 {-1,0}, {0,1}, {1,0}, {0,-1} 还是反过来，对是否能到达终点毫无影响，但会影响第一次到达某点的路径长度（这个长度始终是最短的）和具体走哪条最短路。

性能上无差异；兼容性也没问题——所有 C++ 标准都保证 std::queue 的 FIFO 行为。