## 引入

BFS（广度优先搜索）为图论中的基础算法，详见 [BFS（图论）](../graph/bfs.md) 页面．在 **搜索算法** 中，该算法通常指利用队列结构逐层扩展状态的搜索方式，与图论中的 BFS 算法思想一致，特别适合求解 **最短路径** 或 **最少步骤** 类问题．

## 解释

BFS 的核心思想是 **按层扩展**，从起点开始逐层扫描可到达的位置．首次遇到终点时的路径长度即为最短路径．这种方式保证了搜索的层次性与最优性．

在实际执行中，BFS 会从起点出发，先访问起点的所有直接可到达结点，这些可到达结点构成了搜索的第一层；接着，再以这些可到达结点为新的起点，依次访问它们的邻居，形成第二层；以此类推，不断向外扩展，直至找到目标结点或遍历完所有可达结点．这个过程中，算法会借助队列和访问数组，将每一层新发现的结点（访问数组中还没有记录过的）依次入队，确保同一层的结点按照访问顺序依次被处理，从而严格遵循「按层扩展」的逻辑．

BFS 非常擅于快速求解 **最短路径** 或 **最少步骤**．当算法在某一层首次遇到目标时，此时经过的路径长度（步骤数）必然是最短的．这是因为 BFS 算法的「按层扩展」机制保证了每个结点都是通过最少的步数被访问到：就像从起点出发，沿着最直接的路径不断搜索，直到抵达终点，不会出现绕路或走多余步骤的情况．在这类问题中，BFS 通常也比 DFS 的效率更高．

但是，相较于 DFS，BFS 也有其缺点．通常情况下，BFS 需要更大的内存，缺乏天然的回溯过程，且深度剪枝相对没有 DFS 灵活．

## 例题

???+ example "例题 [Luogu B3625 迷宫寻路](https://www.luogu.com.cn/problem/B3625)"
    在一个 $n \times m$ 的迷宫矩阵中，`.` 表示可通行区域，`#` 表示障碍物．从起点 $(1,1)$ 出发，每次可向上下左右四个方向移动，问是否能到达终点 $(n,m)$．

??? note "解答"
    实现时需要维护一个队列来存储待处理的坐标，并配合访问标记数组避免重复计算．一个结点扩展可到达结点的时候，需要向上下左右拓展，这四个方向分别为 $(x, y + 1)$，$(x, y - 1)$，$(x + 1, y)$，$(x - 1, y)$，在代码中使用了方向数组．注意判断不能拓展到有障碍物的位置．

??? note "参考实现"
    ```cpp
    --8<-- "docs/search/code/bfs/bfs-1.cpp"
    ```

???+ example "例题 [Luogu P1135 奇怪的电梯](https://www.luogu.com.cn/problem/P1135)"
    有 $n$ 层楼和一架电梯．电梯位于第 $i$ 层楼时，向上或向下移动的层数等于一个固定的数字 $k_i$．如果到达的层数不合法，即不在 $1$ 和 $n$ 之间，相应的操作就无法进行．问：从第 $a$ 楼到第 $b$ 楼至少操作几次电梯？如果无法到达，输出 $-1$．

??? note "解答"
    本题需要计算最短路径，这正是 BFS 擅长解决的问题．实现时，需要在队列中同时维护需要处理的楼层位置和从起点 $a$ 出发到达当前楼层的最短距离，并配合访问标记数组避免重复加入同一个元素．一个结点 $i$ 扩展可到达结点的时候，需要向 $i + k_i$ 和 $i - k_i$ 扩展，注意不能到达非法楼层．当扩展到尚未到达的合法楼层时，需要将它加入队列，并记录到达该楼层的最短距离为到达当前所在楼层的最短距离加一．当首次到达结点 $b$ 时，记录的最短距离就是最终答案．
    
    代码中，直接记录距离数组，并利用距离是否为默认值（即 $-1$）来判断结点是否尚未访问．

??? note "参考实现"
    ```cpp
    --8<-- "docs/search/code/bfs/bfs-2.cpp"
    ```

## 习题

-   [Luogu P1443 马的遍历](https://www.luogu.com.cn/problem/P1443)
-   [Luogu P3956 \[NOIP 2017 普及组\] 棋盘](https://www.luogu.com.cn/problem/P3956)
-   [Luogu P1126 机器人搬重物](https://www.luogu.com.cn/problem/P1126)
