02、广度优先搜索

继续来给大家说一下广度优先搜索

广度优先搜索（BFS）

核心思想

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

策略：
1. 从起点出发，先访问所有距离为 1 的节点
2. 再访问所有距离为 2 的节点
3. 依次类推，像水波纹一样扩散
4. 直到所有节点都访问过

特点：
- 使用队列（Queue）实现
- 空间复杂度：O(w)，w 是最大宽度
- 适合：最短路径、层次遍历、最小步数

听着好像不太好懂，我们继续通过一个例子来描述

优惠券逐层分享
第0天：1个初始用户拿到奶茶店优惠券（起点）
第1天：初始用户分享给身边的直接好友（第一层）
第2天：这些领到券的好友，再各自分享给他们的直接好友（第二层）
第3天：新领到券的人继续分享给各自的直接好友（第三层）
...

每一天就是一层，先分享给最近的直接好友，再逐层分享给更远的人。

这就是 BFS 的思想！

图解示例

树的BFS

树结构：
        1
       / \
      2   3
     / \   \
    4   5   6

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

BFS 遍历过程：

初始状态：
queue = [1]
visited = {}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 0 层：
queue = [1]
        1 ← 出队
       / \
      2   3
     / \   \
    4   5   6

访问 1，将其子节点入队
queue = [2, 3]
visited = {1}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 1 层：
queue = [2, 3]
        1
       / \
      2   3 ← 准备处理
     / \   \
    4   5   6

出队 2，访问，将子节点入队
queue = [3, 4, 5]
visited = {1, 2}

出队 3，访问，将子节点入队
queue = [4, 5, 6]
visited = {1, 2, 3}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

第 2 层：
queue = [4, 5, 6]
        1
       / \
      2   3
     / \   \
    4   5   6 ← 准备处理

出队 4，访问
queue = [5, 6]
visited = {1, 2, 3, 4}

出队 5，访问
queue = [6]
visited = {1, 2, 3, 4, 5}

出队 6，访问
queue = []
visited = {1, 2, 3, 4, 5, 6}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

BFS 遍历顺序: 1 → 2 → 3 → 4 → 5 → 6

按层次：
第 0 层: 1
第 1 层: 2, 3
第 2 层: 4, 5, 6

图的广度优先搜索，可以看这个图，到这里大家基本就理解的广度优先搜索的含义，下面我们来看一下实现方式吧

BFS 实现

标准队列实现 ⭐

/**
 * BFS 队列实现（树的层次遍历）
 */
void bfs(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

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

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        // 处理当前节点
        cout << node->val << " ";

        // 将子节点入队
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

/**
 * BFS 队列实现（图的遍历）
 */
void bfs(int start, vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;

    // 起点入队并标记
    q.push(start);
    visited[start] = true;

    // 队列不空时循环
    while (!q.empty()) {
        // 取出队首元素
        int node = q.front();
        q.pop();

        // 处理当前节点
        cout << node << " ";

        // 将所有未访问的邻居入队
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;  // 入队时就标记，避免重复入队
            }
        }
    }
}

BFS 模板总结

/**
 * 基础模板 ⭐⭐⭐
 */
void bfs(起点) {
    queue<节点类型> q;
    set/vector visited;

    // 起点入队
    q.push(起点);
    visited.insert(起点);

    // 循环处理
    while (!q.empty()) {
        // 取出队首
        节点 node = q.front();
        q.pop();

        // 处理当前节点
        // ...

        // 扩展下一层
        for (邻居 : node的所有邻居) {
            if (邻居未访问) {
                q.push(邻居);
                visited.insert(邻居);
            }
        }
    }
}

BFS 时间与空间复杂度

图的 BFS：
- 时间复杂度：O(V + E)
  V: 顶点数，E: 边数
  每个顶点入队一次，每条边检查一次

- 空间复杂度：O(V)
  队列中最多存储一层的节点
  最坏情况是完全图的最后一层

树的 BFS：
- 时间复杂度：O(n)
  n 是节点数

- 空间复杂度：O(w)
  w 是树的最大宽度
  完全二叉树最后一层：约 n/2