广度优先搜索BFS：一层一层地扩散

? 广度优先搜索：像水波一样，一圈一圈找到最短路径

当你往平静的湖面丢一颗石子，水面会泛起一圈一圈的波纹，从落点向外扩散。广度优先搜索（BFS） 就是计算机模仿这种“水波扩散”的方法：先访问离起点最近的所有位置，再访问第二近的，依此类推。它的最大特点是：当你第一次遇到目标时，走过的步数一定是最少的——也就是说，BFS能帮我们找到最短路径。

比如你和朋友们玩“传话游戏”：你站在操场中央，先喊一声，让离你最近的5个朋友听到，然后他们再喊一声，让离他们最近的人听到。这样消息就像波纹一样一圈圈传开。最先听到消息的人，一定是离你最近的那一圈里的一个。BFS 就是这样一层一层地“传话”，直到找到目标。

在写游戏 AI（比如走迷宫、地图寻路）、网络爬虫（一层层爬取网页）或者社交网络（找到两个人的最短距离）时，BFS 都是非常常用的工具。

? BFS 是怎么工作的

1. 搜索过程：从起点向外一圈一圈扩

想象一个 5×5 的网格，起点在左上角 (0,0)，终点（比如 9）在右下角附近。BFS 会这样探索：

第 0 圈：起点 (0,0) 本身。
第 1 圈：所有与起点相邻（上下左右）且能走的位置。
第 2 圈：所有与第 1 圈位置相邻且未访问过的位置。
……

直到某一次遇到终点，这时走的圈数就是起点到终点的最短步数。

2. 关键工具：队列（先进先出）

BFS 用队列（queue） 来管理“下一圈要探索的位置”。队列就像排队买奶茶：先来的人先服务，后来的人排后面。我们把起点放进队列，然后：

从队列取出队首位置（当前正在探索的位置）。
把它的所有未被访问过的邻居加入队尾（这些邻居会在下一轮被探索）。
重复直到队列为空（全部探索完）或者找到目标。

忘记标记已访问
把邻居加入队列后，立刻标记 visited。如果等到从队列取出时才标记，可能同一个位置被加入队列多次，导致重复计算甚至死循环。
队列使用不当
- 忘了 pop()：队列会越来越长，程序不结束。
- 忘了 push()：邻居没加进去，搜索不完整。
边界与障碍判断漏掉
一定要先检查新位置是否在迷宫范围内（nx >= 0 && nx < 行数 等），再检查是不是障碍（maze[nx][ny] != 1）。顺序错了可能导致数组越界。
误以为 BFS 可以回溯
BFS 不回溯，因为第一次访问就是最短路径。不需要像 DFS 那样“标记-取消标记”。

? 完整可运行的代码示例

下面的代码用 BFS 在同一个迷宫中寻找最短路径（迷宫中的 0 表示空地，1 表示墙壁，9 表示出口）。运行后会输出最短步数。

#include <iostream>
#include <queue>      // 使用队列
using namespace std;

// 迷宫地图：0=空地，1=墙，9=出口
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 9},   // 出口在 (2,4)
    {0, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};

int visited[5][5] = {0};      // 0=未访问，1=已访问
int step[5][5] = {0};         // 记录从起点到每个位置的最短步数

// 四个方向：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// BFS 函数：起点 (sx, sy)，返回最短步数，-1 表示无路
int bfs(int sx, int sy) {
    queue<pair<int, int>> q;   // 队列存储坐标 (x,y)
    q.push({sx, sy});          // 起点入队
    visited[sx][sy] = 1;       // 标记起点已访问
    step[sx][sy] = 0;          // 起点步数为 0

    while (!q.empty()) {
        // 取出队首位置
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        // 如果当前位置是出口，直接返回步数（一定是第一次到达，所以最短）
        if (maze[x][y] == 9) {
            return step[x][y];
        }

        // 尝试四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 判断新位置是否合法：在范围内、不是墙、未访问
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 
                && maze[nx][ny] != 1 && !visited[nx][ny]) {
                visited[nx][ny] = 1;               // 标记已访问
                step[nx][ny] = step[x][y] + 1;     // 步数 = 上一步 + 1
                q.push({nx, ny});                  // 新位置入队
            }
        }
    }
    return -1;   // 队列为空还没找到出口，说明无路
}

int main() {
    int steps = bfs(0, 0);   // 从左上角 (0,0) 出发
    if (steps != -1) {
        cout << "最短路径长度：" << steps << endl;
    } else {
        cout << "没有路径" << endl;
    }
    return 0;
}

运行结果：
最短路径长度：7 （因为从 (0,0) 到 (2,4) 的最短路径需要走 7 步）

你可以自己修改迷宫，比如把出口移到别处，或者增加墙壁，看看 BFS 能不能找到最短路径。试试把起点换成 (0,0)，出口换成 (4,4)（目前是墙 1），会输出“没有路径”。

? 相关知识点指引

深度优先搜索（DFS）：与 BFS 不同，DFS 一条路走到底，适合判断是否可达，但找最短路径时可能不是最优。
队列（queue）：BFS 的核心数据结构，理解先进先出很重要。
图遍历：BFS 不仅用于网格迷宫，也用于普通图（用邻接表或邻接矩阵存储）。
二维数组与方向数组：dx/dy 技巧在搜索中非常常用，可以让代码更简洁。

如果你已经掌握了 BFS，可以试试更复杂的题目，比如“走迷宫带传送门”、“多个起点同时搜索”或者“用 BFS 求八数码问题的最少步数”。祝你编程路上越走越远！

? 广度优先搜索：像水波一样，一圈一圈找到最短路径

? BFS 是怎么工作的

1. 搜索过程：从起点向外一圈一圈扩

2. 关键工具：队列（先进先出）

3. 标记已访问：避免重复绕路

4. 记录步数：一路记下走了几步

❌ 新手常犯的错误

? 完整可运行的代码示例

? 相关知识点指引

例题精讲