一、算法概述

广度优先搜索（Breadth-First Search，BFS）是一种按层遍历图或树的算法。它从起点出发，先访问所有距离起点为 1 的节点，再访问距离为 2 的节点，以此类推，逐层向外扩展。BFS 是求解无权图最短路径的标准方法。

二、核心思想

BFS 的核心思想是**"逐层扩散"**：

1. 从起点开始，将其加入队列
2. 每次从队列头部取出一个节点，访问其所有未访问过的邻接节点，将它们加入队列尾部
3. 重复第 2 步，直到队列为空

由于 BFS 是按距离递增的顺序访问节点的，因此首次访问到某个节点时所经过的路径，就是从起点到该节点的最短路径（前提是边权均为 1 或无权图）。

• 关键数据结构：队列（FIFO）
• 辅助数组：visited[] 标记访问状态，dist[] 记录距离

三、算法步骤/伪代码

BFS(起点 s):
    创建队列 q
    visited[s] = true
    dist[s] = 0
    将 s 入队

    while q 非空:
        u = q.front(), q.pop()
        for 每个与 u 相邻的节点 v:
            if v 未被访问:
                visited[v] = true
                dist[v] = dist[u] + 1   // 记录距离
                q.push(v)

多起点 BFS

将多个起点同时入队并标记已访问，然后执行正常的 BFS 流程，即可同时从多个源点向外扩展。这常用于"同时从多个起点出发"的场景（如岛屿数量用 BFS）。

四、C++ 代码实现

以下包含两个完整可运行的示例：迷宫最短路径 和 树的层序遍历。

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

// ==================== 示例1：迷宫最短路径（BFS求最少步数） ====================
class MazeSolver {
public:
    // 0=空地, 1=障碍物。返回从 (sx,sy) 到 (ex,ey) 的最少步数，不可达返回 -1
    static int shortestPath(vector<vector<int>>& maze,
                            int sx, int sy, int ex, int ey) {
        int rows = maze.size();
        int cols = maze[0].size();

        // 起点或终点被障碍物阻挡
        if (maze[sx][sy] == 1 || maze[ex][ey] == 1) return -1;

        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
        queue<pair<int, int>> q;

        dist[sx][sy] = 0;
        q.push({sx, sy});

        // 四个方向：上、下、左、右
        const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            // 到达终点
            if (r == ex && c == ey) return dist[r][c];

            for (auto& d : dirs) {
                int nr = r + d[0];
                int nc = c + d[1];
                // 边界检查 + 障碍物检查 + 未访问检查
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                    maze[nr][nc] == 0 && dist[nr][nc] == INT_MAX) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push({nr, nc});
                }
            }
        }
        return -1; // 不可达
    }
};

// ==================== 示例2：二叉树层序遍历（LeetCode 102） ====================
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
};

class LevelOrderTraversal {
public:
    // 层序遍历：返回每层节点的值
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();  // 当前层的节点数
            vector<int> level;
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

// ==================== 主函数 ====================
int main() {
    // ----- 迷宫最短路径演示 -----
    cout << "========== 迷宫最短路径 ==========" << endl;
    vector<vector<int>> maze = {
        {0, 0, 0, 1, 0},
        {1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };
    int sx = 0, sy = 0;  // 起点 (0,0)
    int ex = 4, ey = 4;  // 终点 (4,4)

    cout << "迷宫 (0=空地, 1=障碍):" << endl;
    for (auto& row : maze) {
        for (int v : row) cout << v << " ";
        cout << endl;
    }

    int steps = MazeSolver::shortestPath(maze, sx, sy, ex, ey);
    cout << "从 (" << sx << "," << sy << ") 到 (" << ex << "," << ey << ") ";
    if (steps == -1)
        cout << "不可达" << endl;
    else
        cout << "最少步数: " << steps << endl;

    // ----- 二叉树层序遍历演示 -----
    cout << "\n========== 二叉树层序遍历 ==========" << endl;
    // 构建二叉树:
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root = new TreeNode(3,
        new TreeNode(9),
        new TreeNode(20,
            new TreeNode(15),
            new TreeNode(7)
        )
    );

    LevelOrderTraversal lot;
    auto levels = lot.levelOrder(root);
    cout << "层序遍历结果:" << endl;
    for (int i = 0; i < (int)levels.size(); ++i) {
        cout << "第" << i + 1 << "层: ";
        for (int v : levels[i]) cout << v << " ";
        cout << endl;
    }

    // 释放内存
    delete root->right->left;
    delete root->right->right;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

五、复杂度分析

• 时间复杂度：$\mathbf{O(V + E)}$

  • 每个节点入队出队一次：$O(V)$
  • 每条边在其端点被出队时检查一次：$O(E)$

• 空间复杂度：$\mathbf{O(V)}$

  • 队列中最多同时存放一层节点（最坏 $O(V)$）
  • visited / dist 数组：$O(V)$

六、应用场景

场景	说明
无权图最短路径	BFS 首次访问即最短路径，天然适合求最少步数
层序遍历	按层输出树/图的节点
连通性检测	与 DFS 等价，可以用 BFS 判断连通分量个数
迷宫最短步数	二维网格中搜索最少步数
社交网络中的"度数"	在n度人脉中寻找目标用户
多源BFS	多个起点同时开始 BFS（如腐烂橘子、01矩阵）
拓扑排序	基于入度（Kahn算法）的 BFS 变体
双向BFS	从起点和终点同时 BFS，中间相遇时即为最短路径，常用于搜索优化

七、经典例题

例题1：二叉树的层序遍历（LeetCode 102）

上述代码中 LevelOrderTraversal 类即为完整实现。核心技巧：利用 levelSize = q.size() 控制逐层处理。

---

例题2：岛屿数量（LeetCode 200 —— BFS 解法）

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

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int rows = grid.size(), cols = grid[0].size();
        int count = 0;
        const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    ++count;
                    // BFS 遍历该岛屿
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    grid[i][j] = '0'; // 入队即标记
                    while (!q.empty()) {
                        auto [r, c] = q.front();
                        q.pop();
                        for (auto& d : dirs) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                                && grid[nr][nc] == '1') {
                                grid[nr][nc] = '0';
                                q.push({nr, nc});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};

int main() {
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    Solution sol;
    cout << "岛屿数量(BFS): " << sol.numIslands(grid) << endl; // 输出: 3
    return 0;
}

---

例题3：迷宫最短步数

上述 MazeSolver::shortestPath 即为完整实现。BFS 保证了首次到达终点时的步数一定是最小值。