BFS（搜索）
引入
BFS（广度优先搜索）为图论中的基础算法，详见 BFS（图论） 页面．在 搜索算法 中，该算法通常指利用队列结构逐层扩展状态的搜索方式，与图论中的 BFS 算法思想一致，特别适合求解 最短路径 或 最少步骤 类问题．
解释
BFS 的核心思想是 按层扩展 ，从起点开始逐层扫描可到达的位置．首次遇到终点时的路径长度即为最短路径．这种方式保证了搜索的层次性与最优性．
在实际执行中，BFS 会从起点出发，先访问起点的所有直接可到达结点，这些可到达结点构成了搜索的第一层；接着，再以这些可到达结点为新的起点，依次访问它们的邻居，形成第二层；以此类推，不断向外扩展，直至找到目标结点或遍历完所有可达结点．这个过程中，算法会借助队列和访问数组，将每一层新发现的结点（访问数组中还没有记录过的）依次入队，确保同一层的结点按照访问顺序依次被处理，从而严格遵循「按层扩展」的逻辑．
BFS 非常擅于快速求解 最短路径 或 最少步骤 ．当算法在某一层首次遇到目标时，此时经过的路径长度（步骤数）必然是最短的．这是因为 BFS 算法的「按层扩展」机制保证了每个结点都是通过最少的步数被访问到：就像从起点出发，沿着最直接的路径不断搜索，直到抵达终点，不会出现绕路或走多余步骤的情况．在这类问题中，BFS 通常也比 DFS 的效率更高．
但是，相较于 DFS，BFS 也有其缺点．通常情况下，BFS 需要更大的内存，缺乏天然的回溯过程，且深度剪枝相对没有 DFS 灵活．
例题
在一个 𝑛 ×𝑚n×m
的迷宫矩阵中，. 表示可通行区域，# 表示障碍物．从起点 (1,1)(1,1) 出发，每次可向上下左右四个方向移动，问是否能到达终点 (𝑛,𝑚)(n,m)．
解答
实现时需要维护一个队列来存储待处理的坐标，并配合访问标记数组避免重复计算．一个结点扩展可到达结点的时候，需要向上下左右拓展，这四个方向分别为 (𝑥,𝑦 +1)(x,y+1)，(𝑥,𝑦 −1)(x,y−1)，(𝑥 +1,𝑦)(x+1,y)，(𝑥 −1,𝑦)(x−1,y)，在代码中使用了方向数组．注意判断不能拓展到有障碍物的位置．
参考实现
---|---
例题 [Luogu P1135 奇怪的电梯](https://www.luogu.com.cn/problem/P1135)
有 𝑛n 层楼和一架电梯．电梯位于第 𝑖i 层楼时，向上或向下移动的层数等于一个固定的数字 𝑘𝑖ki．如果到达的层数不合法，即不在 11 和 𝑛n 之间，相应的操作就无法进行．问：从第 𝑎a 楼到第 𝑏b 楼至少操作几次电梯？如果无法到达，输出 −1−1．
解答
本题需要计算最短路径，这正是 BFS 擅长解决的问题．实现时，需要在队列中同时维护需要处理的楼层位置和从起点 𝑎a 出发到达当前楼层的最短距离，并配合访问标记数组避免重复加入同一个元素．一个结点 𝑖i 扩展可到达结点的时候，需要向 𝑖 +𝑘𝑖i+ki 和 𝑖 −𝑘𝑖i−ki 扩展，注意不能到达非法楼层．当扩展到尚未到达的合法楼层时，需要将它加入队列，并记录到达该楼层的最短距离为到达当前所在楼层的最短距离加一．当首次到达结点 𝑏b 时，记录的最短距离就是最终答案．
代码中，直接记录距离数组，并利用距离是否为默认值（即 −1−1）来判断结点是否尚未访问．
参考实现
---|---
习题
- Luogu P1443 马的遍历
- [Luogu P3956 [NOIP 2017 普及组] 棋盘](https://www.luogu.com.cn/problem/P3956)
- Luogu P1126 机器人搬重物
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Anguei, c-forrest, vincent-163, ChungZH, Enter-tainer, ksyx, ouuan, Qlgdgasdx, Tiphereth-A, TrisolarisHD, Xeonacid, ylxmf2005 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用