BFS能保证最短路径是因为其按层扩展，首次访问目标节点时的层数即为最少边数；关键在于入队时标记访问、用队列实现逐层推进、记录前驱以还原路径，且仅适用于边权相等的图。
广度优先搜索（BFS）天然适合求解无权图中从起点到终点的最短路径——它按层扩展，第一次到达目标节点时所经步数一定最少。关键不在于“有没有路”，而在于“哪条路最近”。队列是实现逐层推进的核心结构，而“最优联通解”本质上就是最早在某一层中被发现的合法可达路径。
为什么BFS能保证最短？
BFS严格遵循“距离递增”原则：所有与起点距离为 k 的节点，必然在第 k 层被统一访问。一旦目标节点在第 d 层首次出现，就说明不存在更短的路径（否则它会在更早的层被发现）。这和加权图中需用 Dijkstra 的情况不同——BFS 的“最短”特指边数最少，即跳数最少。
队列怎么用才不丢路径信息？
单纯遍历节点不够，要还原完整路径，需额外记录每个节点的前驱（parent）或使用路径数组：
- 每入队一个新节点，同时记录它是从哪个节点“走过来”的；
- 当目标节点出队时，沿 parent 指针反向回溯，即可得到从起点到终点的最短路径；
- 避免用递归回溯，推荐用数组
path[i] = j表示节点i的前驱是j，起点的前驱设为 -1。
实际编码要注意的细节
几个容易出错但影响结果的关键点：
- 访问标记必须在入队时打，而非出队时——否则同一节点可能被多个邻居重复加入队列；
- 图可能含环或双向边，未及时标记已访问会导致无限循环；
- 若存在多个等长最短路径，BFS 默认返回其中任意一条（取决于邻接表顺序），如需全部路径，需改用路径枚举策略，不再是标准 BFS；
- 二维网格（如迷宫）中，上下左右四个方向移动，可统一用方向数组
[(-1,0),(0,1),(1,0),(0,-1)]简化坐标更新。
什么场景下别硬套BFS？
BFS虽能找最短路径，但不是万能解：
- 图带边权？→ 改用 Dijkstra 或 A*；
- 只关心“是否连通”，不要路径？→ 可简化为布尔型 visited 数组 + 队列，无需存 parent；
- 空间受限且图极宽（比如社交网络中百万好友）？→ BFS 内存开销大（O(宽度)），此时可考虑双向 BFS 或迭代加深；
- 目标离起点很远，而图稀疏？→ DFS + 剪枝可能更快，但无法保证最短。
