docs/search/bfs.md
BFS（广度优先搜索）为图论中的基础算法，详见 BFS（图论） 页面．在 搜索算法 中，该算法通常指利用队列结构逐层扩展状态的搜索方式，与图论中的 BFS 算法思想一致，特别适合求解 最短路径 或 最少步骤 类问题．
BFS 的核心思想是 按层扩展，从起点开始逐层扫描可到达的位置．首次遇到终点时的路径长度即为最短路径．这种方式保证了搜索的层次性与最优性．
在实际执行中，BFS 会从起点出发，先访问起点的所有直接可到达结点，这些可到达结点构成了搜索的第一层；接着，再以这些可到达结点为新的起点，依次访问它们的邻居，形成第二层；以此类推，不断向外扩展，直至找到目标结点或遍历完所有可达结点．这个过程中，算法会借助队列和访问数组，将每一层新发现的结点（访问数组中还没有记录过的）依次入队，确保同一层的结点按照访问顺序依次被处理，从而严格遵循「按层扩展」的逻辑．
BFS 非常擅于快速求解 最短路径 或 最少步骤．当算法在某一层首次遇到目标时，此时经过的路径长度（步骤数）必然是最短的．这是因为 BFS 算法的「按层扩展」机制保证了每个结点都是通过最少的步数被访问到：就像从起点出发，沿着最直接的路径不断搜索，直到抵达终点，不会出现绕路或走多余步骤的情况．在这类问题中，BFS 通常也比 DFS 的效率更高．
但是，相较于 DFS，BFS 也有其缺点．通常情况下，BFS 需要更大的内存，缺乏天然的回溯过程，且深度剪枝相对没有 DFS 灵活．
???+ example "例题 Luogu 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 奇怪的电梯" 有 $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"