广度优先搜索

广度优先搜索（Breadth-First Search, BFS）是一种 ​​层序遍历​​ 的算法，适用于解决 ​​最短路径​​、​​最小步数​​、​​状态空间探索​​ 等问题。

BFS 适用于以下场景：

• ​​求最短路径或最少操作步数​​（如迷宫最短路径、单词接龙）。
• ​​状态转换问题​​（如八数码问题、密码锁破解）。
• ​​图的连通性判断​​（如岛屿数量、社交网络好友关系）。

BFS 核心四步框架​​

1. 初始化队列和访问标记​​
   • ​​队列​​：存储待处理的节点（通常用 deque实现）。
   • ​​访问标记​​：避免重复访问（数组、哈希表或位掩码）。
2. 定义状态扩展规则​​
   • ​子节点生成​​：根据问题定义如何从当前状态扩展到下一状态。
   • 方向控制​​：如网格问题中的上下左右移动，或状态转换问题中的操作集合。
3. 层序遍历与终止条件​​
   • ​逐层处理​​：每次处理一层的所有节点。
   • 终止条件​​：找到目标状态或队列为空。
4. 记录路径或步数（可选）​​
   • ​​步数统计​​：每层循环后步数加一。
   • 路径回溯​​：通过父指针字典反向追踪路径。