广度优先搜索（BFS）——像涟漪一样一层层扩散

想象你往平静的湖面丢下一颗石子，水波会一圈一圈向外扩散，先碰到最近的岸边，再缓缓扩散到更远的地方。广度优先搜索（BFS） 就是按照这种“同心圆”的方式工作的搜索算法：从起点出发，先检查所有“一步就能到”的点，再检查“两步才能到”的点，依此类推，直到找到目标或者把所有可达的点都访问完毕。

BFS 最擅长的就是解决 “从起点到终点最少需要几步” 的问题，比如：在迷宫里找最短路线、在社交网络中找两个人之间最少通过几个朋友认识、在地图上找从家到学校的最短路径……它就像个耐心的快递员，先送完所有距离近的客户，再送远一点的，保证每个包裹都按距离优先送达。

1. BFS 的核心思想：一层一层，不慌不忙

和它的好兄弟 深度优先搜索（DFS） 不同，DFS 喜欢一条路走到黑，撞到墙再回头；而 BFS 则像“地毯式排查”——先把起点周围所有方向都看一遍，记下来，然后逐个处理这些新位置，再继续看它们周围的新方向……这样一圈一圈地扩散，最先找到的目标往往就是距离最短的那个。

生活中的比喻：传话游戏 假设班长接到一个紧急通知，需要告诉全班同学。他先把消息告诉身边的几个好朋友（一步距离），这些好朋友又分别告诉自己的朋友（两步距离），消息就这样一层层传开，绝不跳过任何人，也不会有人被重复通知。如果有同学同时被两个人通知，就只算一次。最终，每个同学都会在“最短的传话次数”内收到消息。

用队列来模拟“排队” 要实现这种“一层层”的效果，我们需要一个 队列（queue） 来记住待处理的任务。队列就像电影院买票的队伍：先排队的人先离开（先进先出）。在 BFS 中，我们先把起点放进队列，然后循环：每次从队首取出一个位置，处理它（比如输出或记录），再把它所有没去过的新邻居放进队尾。这样，先入队的邻居会先被处理，也就是离起点更近的点会先被访问，从而实现“一层一层”扩散。

2. 新手最容易犯的错误

忘记把访问过的点标记起来
如果访问了一个位置后不记录，后面可能会再次从其他路走过来，导致死循环。就像传话游戏中，如果已经告诉过小明，就不能再让另一个人再告诉他一遍，否则消息会反复传。
忘记从队列中删除元素
如果只 q.front() 而不 q.pop()，队列永远不为空，会无限循环。
没有处理空节点或越界
在树或图中，有些节点可能不存在（比如用 -1 表示空），如果不跳过，程序可能崩溃。
忽略队列为空的情况
如果在 while 循环外直接取队首，而队列可能为空，会导致错误。

3. 一步一步写代码：用 BFS 遍历一棵树

我们先复习一下树的结构。下面这棵树（用数组存储）：

用 BFS 遍历的结果应该是：0 → 1 → 2 → 3 → 4 → 5 → 6 → 7（按层输出）。

#include <iostream>
#include <queue>        // 使用队列需要的头文件
using namespace std;

const int N = 10;       // 最多10个节点
// 左孩子数组，-1表示没有左孩子
int leftChild[N] = {1, 3, 5, 7, -1, -1, -1, -1, -1, -1};
// 右孩子数组，-1表示没有右孩子
int rightChild[N] = {2, 4, 6, -1, -1, -1, -1, -1, -1, -1};

void bfs(int start) {
    queue<int> q;               // 创建一个空队列，用来存放待处理的节点编号
    q.push(start);              // 把起点（根节点）放入队列
    while (!q.empty()) {        // 只要队列还有节点，就继续处理
        int node = q.front();   // 取出队列最前面的节点（最先被放进去的）
        q.pop();                // 把它从队列中删除（它已经被处理了）
        if (node == -1) continue;  // 如果节点是空的（-1），跳过它
        cout << node << " ";    // 访问当前节点，比如打印出来
        // 把它的左孩子和右孩子加入队列（如果存在），以后会按顺序处理
        q.push(leftChild[node]);   // 左孩子入队
        q.push(rightChild[node]);  // 右孩子入队
    }
}

int main() {
    cout << "BFS遍历结果: ";
    bfs(0);                     // 从根节点0开始遍历
    cout << endl;
    return 0;
}

运行结果：

BFS遍历结果: 0 1 2 3 4 5 6 7

看到区别了吗？BFS 先输出 0，然后输出它的两个孩子 1 和 2，然后输出 1 的孩子 3 和 4，再输出 2 的孩子 5 和 6，最后输出 3 的孩子 7。一层一层，整齐有序。

4. 另一个经典例子：用BFS走出迷宫（求最短步数）

假设有一个 4×4 的迷宫，0 表示空地可以走，1 表示墙不能走。起点在 (0,0)，终点在 (3,3)。我们要用 BFS 找出从起点到终点最少需要走多少步。

BFS 会从起点开始，向上下左右四个方向扩散，每扩散一层就步数加 1。第一次到达终点时，那一步数就是最短路径长度。

#include <iostream>
#include <queue>
using namespace std;

const int ROWS = 4, COLS = 4;
// 迷宫：0可走，1墙
int maze[ROWS][COLS] = {
    {0, 0, 1, 0},
    {0, 0, 0, 0},
    {0, 1, 0, 1},
    {0, 0, 0, 0}
};
// 四个方向：上、下、左、右（用行和列的变化表示）
int dir_row[4] = {-1, 1, 0, 0}; // 行的变化
int dir_col[4] = {0, 0, -1, 1}; // 列的变化
// 记录每个位置是否已经访问过（初始化为false）
bool visited[ROWS][COLS] = {false};
// 记录从起点到每个位置的最短步数（初始化为0）
int step[ROWS][COLS] = {0};

int bfs(int sRow, int sCol, int eRow, int eCol) {
    // 队列里存的是坐标，可以用pair，也可以自己定义结构体
    queue<pair<int, int>> q;        // 队列每个元素是 (行,列)
    q.push({sRow, sCol});           // 起点入队
    visited[sRow][sCol] = true;     // 标记起点已访问
    step[sRow][sCol] = 0;           // 起点步数为0

    while (!q.empty()) {
        // 取出当前队首的坐标
        int cur_row = q.front().first;
        int cur_col = q.front().second;
        q.pop();                    // 删除队首

        // 检查是否到达终点
        if (cur_row == eRow && cur_col == eCol) {
            return step[cur_row][cur_col]; // 返回最短步数
        }

        // 尝试向四个方向走
        for (int i = 0; i < 4; i++) {
            int new_row = cur_row + dir_row[i];
            int new_col = cur_col + dir_col[i];

            // 检查新位置是否在迷宫内、不是墙、且没有访问过
            if (new_row >= 0 && new_row < ROWS &&
                new_col >= 0 && new_col < COLS &&
                maze[new_row][new_col] == 0 &&
                !visited[new_row][new_col]) {
                
                visited[new_row][new_col] = true;      // 标记已访问
                step[new_row][new_col] = step[cur_row][cur_col] + 1; // 步数增加1
                q.push({new_row, new_col});            // 新位置入队
            }
        }
    }
    return -1; // 如果队列空了还没到终点，说明无路可走
}

int main() {
    int result = bfs(0, 0, 3, 3);
    if (result != -1) {
        cout << "从起点到终点最少需要 " << result << " 步。\n";
    } else {
        cout << "无法到达终点。\n";
    }
    return 0;
}

运行结果：

从起点到终点最少需要 6 步。

（你可以自己画一画地图，验证一下这条最短路径是不是6步。）

5. 完整可运行的 BFS 综合示例（附注释）

下面是一个完整的、可以直接复制运行的代码，它包含了上面两个例子（树遍历和迷宫最短路径）以及一个简单的测试。你可以修改迷宫大小或树的结构，观察 BFS 的行为。

#include <iostream>
#include <queue>
using namespace std;

// 第一部分：BFS 遍历树（与上面一致）
void bfs_tree() {
    const int N = 10;
    int leftChild[N] = {1, 3, 5, 7, -1, -1, -1, -1, -1, -1};  // 左孩子
    int rightChild[N] = {2, 4, 6, -1, -1, -1, -1, -1, -1, -1}; // 右孩子

    queue<int> q;
    q.push(0);      // 根节点入队
    cout << "树 BFS: ";
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        if (node == -1) continue;
        cout << node << " ";
        q.push(leftChild[node]);
        q.push(rightChild[node]);
    }
    cout << endl;
}

// 第二部分：迷宫最短路径
int bfs_maze() {
    const int R = 4, C = 4;
    int maze[R][C] = {
        {0, 0, 1, 0},
        {0, 0, 0, 0},
        {0, 1, 0, 1},
        {0, 0, 0, 0}
    };
    bool visited[R][C] = {false};
    int step[R][C] = {0};
    int dir_r[4] = {-1, 1, 0, 0}; // 上下左右
    int dir_c[4] = {0, 0, -1, 1};

    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    step[0][0] = 0;

    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        // 到达终点
        if (r == 3 && c == 3) return step[r][c];

        for (int i = 0; i < 4; i++) {
            int nr = r + dir_r[i];
            int nc = c + dir_c[i];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C &&
                maze[nr][nc] == 0 && !visited[nr][nc]) {
                visited[nr][nc] = true;
                step[nr][nc] = step[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return -1; // 无路
}

int main() {
    bfs_tree();                // 树遍历
    int steps = bfs_maze();    // 迷宫最短步数
    if (steps != -1)
        cout << "迷宫最短步数: " << steps << endl;
    else
        cout << "迷宫无解" << endl;
    return 0;
}

6. 什么时候用 BFS？记住这个口诀

问最短，用BFS；问所有，用DFS。

如果问题要求 “最少步数”、“最短时间” 或者 “最早到达”，那 BFS 就是第一选择。
如果问题只要求 “是否存在路径” 或者 “有多少种可能”，DFS 和 BFS 都可以，但 DFS 代码更简洁（可以用递归）。
如果问题要求 “按层处理”（比如打印二叉树的每一层），BFS 是自然选择。

7. 相关知识点指引

学完 BFS 后，你可以继续探索：

深度优先搜索（DFS）：BFS 的好兄弟，适合走迷宫找所有路径、判断连通性等。
队列（queue）：BFS 的核心数据结构，学明白队列的入队、出队、判空。
图的表示：邻接矩阵、邻接表——当你处理更复杂的图时，需要选择合适的方式存储邻居。
优先队列 / Dijkstra 算法：如果边带权重（比如路有长短），BFS 就不够用了，需要更高级的“最短路径算法”。
A 搜索*：在 BFS 基础上加上“启发式”思维，让搜索更快地找到目标。

BFS 是算法世界里最基础也最实用的工具之一，像涟漪一样，一圈一圈地帮助你找到答案。快打开编译器，自己写一个 BFS 试试吧！

广度优先搜索（BFS）——像丢石头入水，一圈一圈扩散