广度优先搜索（BFS）零基础精讲

一、BFS 核心认知：从本质到特点

1.1 定义

广度优先搜索（Breadth-First Search，简称 BFS）是一种适用于树、图、网格的遍历算法，核心逻辑是“先近后远，逐层扩散”——从起点出发，先遍历所有距离为1的节点/格子，再遍历距离为2的，以此类推，绝不跳过当前层深入下一层。

1.2 通俗类比

把起点看作石子投入水中的位置，BFS 就像水面扩散的波纹，一圈一圈向外蔓延，每一圈代表一层遍历，这也是 BFS 能天然求解无权图最短路径的核心原因（每一步距离相等，最先到达目标的路径就是最短）。

1.3 核心特性

• 逐层遍历：严格按层次推进，无跳跃、无回溯

• 最短路径保障：无权图/等权网格中，首次到达目标节点的路径即为最短路径

• 数据结构依赖：必须借助队列（Queue）实现（先进先出，保证层级顺序）

• 访问标记：需标记已访问节点，避免重复入队、死循环

二、BFS 底层逻辑：队列工作流程

队列是 BFS 的“心脏”，遵循“入队-出队-遍历邻接点-标记入队”的闭环逻辑，具体步骤拆解：

1. 初始化：创建队列，将起点加入队列，同时标记起点为“已访问”

2. 循环遍历：只要队列不为空，就持续执行操作

3. 取出队首：弹出队列最前端的节点，作为当前处理节点

4. 遍历邻接