广度优先搜索

一、图论基础：一切的起点

在深入广度优先搜索（BFS）之前，我们必须先理解它所作用的对象——图（Graph）。你可以将图想象成一个由点和线组成的网络。

1.1 什么是图？

一个图 GG 由两个集合组成：一个顶点（Vertex）集合 VV 和一个边（Edge）集合 EE。每条边连接着图中的一对顶点。

  • 顶点（Vertex）：可以看作是图中的节点或对象。例如，在地图上，城市可以被看作顶点。我们通常用 VV 来表示所有顶点的集合。
  • 边（Edge）：表示顶点之间的关系或连接。例如，连接两个城市的公路可以被看作是一条边。我们通常用 EE 来表示所有边的集合。

一条边 e=(u,v)e = (u, v) 连接了顶点 uu 和顶点 vv。

1.2 图的种类

  • 无向图（Undirected Graph）：边没有方向。如果顶点 uu 和 vv 之间有一条边，那么你可以从 uu 到 vv，也可以从 vv 到 uu。这就像一条双向车道。边 (u,v)(u, v) 和 (v,u)(v, u) 是同一条边。

  • 有向图（Directed Graph）：边有方向。如果有一条从 uu 指向 vv 的边，记作 <u,v><u, v>，那么你只能从 uu 到 vv，不能反向。这就像一条单行道。

  • 带权图（Weighted Graph）：每条边都有一个相关的数值，称为“权重”（Weight）。这个权重可以代表距离、时间、成本等。例如，地图上两个城市之间的公路长度。

  • 无权图（Unweighted Graph）：所有边的权重都相同，通常我们认为权重为 11。

BFS 主要应用于无权图，或者说，它在处理问题时会“无视”边的权重，认为每条边的“长度”都是一样的。

1.3 如何表示图？

在计算机中，我们需要一种方式来存储图的结构。最常见的两种方法是邻接矩阵和邻接表。

  • 邻接矩阵（Adjacency Matrix） 我们使用一个二维数组 g[N][N] 来表示图，其中 N 是顶点的最大数量。

    • 对于无权图，如果顶点 ii 和 jj 之间有边，则 g[i][j] = 1，否则为 0。对于无向图，g[i][j] 和 g[j][i] 是对称的。
    • 优点：查询两个点之间是否有边非常快（ O(1)O(1) 时间）。
    • 缺点：当顶点很多但边很少时（称为稀疏图），会浪费大量存储空间。空间复杂度为 O(N2)O(N^2)。

  • 邻接表（Adjacency List） 我们为每个顶点 uu 维护一个列表，这个列表包含了所有与 uu 直接相连的顶点。在C++中，这通常用一个 vector 数组 vector<int> g[N] 来实现。g[u] 存储了所有 uu 可以直接到达的顶点。

    • 优点：只存储存在的边，空间效率高。空间复杂度为 O(N+M)O(N+M)，其中 NN 是点数， MM 是边数。
    • 缺点：查询两个点之间是否有边需要遍历其中一个点的邻接表，时间复杂度最坏为 O(N)O(N)。

在算法竞赛中，由于题目给定的图通常是稀疏图，邻接表是更常用和更高效的选择。

二、广度优先搜索的核心思想

2.1 思想起源：水波涟漪

想象一下，你向平静的湖面中心投下一颗石子。会发生什么？

  1. 石子落水点是第一个被扰动的地方。
  2. 接着，一圈水波会从中心向外扩散，均匀地到达所有与中心距离相同的点。
  3. 然后，这一圈水波又会成为新的波源，激起下一圈更大的水波，继续向外扩散。
  4. 这个过程持续进行，直到水波传遍整个湖面。

广度优先搜索（BFS） 的工作方式与此完全相同。它从一个指定的起始顶点（源点）开始，探索所有与之直接相连的邻居顶点。然后，对于那些邻居顶点，再去探索它们尚未被访问过的邻居顶点。这个过程一层一层地向外展开，就像水波的扩散一样。

核心特征：BFS 是一种逐层的搜索策略。它首先访问所有距离源点为 11 的顶点，然后是所有距离为 22 的顶点，以此类推。这保证了当 BFS 第一次找到目标顶点时，它所经过的路径是最短的（在无权图中，路径长度等于边的数量）。

2.2 与深度优先搜索（DFS）的对比

为了更好地理解 BFS，我们可以将它与另一种常见的搜索算法——深度优先搜索（DFS） 进行对比。

  • BFS（广度/宽度优先）：像水波一样，全面铺开，一层一层地探索。它追求的是“广度”，在深入下一层之前，必须完全探索当前层。
  • DFS（深度优先）：像探险家走迷宫，遇到岔路口就选一条路一直走下去，直到走到死胡同才返回上一个路口，选择另一条路继续探索。它追求的是“深度”，会沿着一条路径尽可能深地探索。

简单来说：

  • BFS：广而浅。
  • DFS：深而窄。

这个根本性的差异决定了它们各自的应用场景。BFS 天然地适用于寻找无权图中的最短路径问题。

三、BFS 的算法实现：队列是关键

如何用代码实现“逐层探索”这一过程呢？答案是使用一种名为队列（Queue） 的数据结构。

3.1 队列（Queue）

队列是一种先进先出（First-In, First-Out, FIFO） 的数据结构。你可以把它想象成一个排队买票的队伍。

  • 入队（Enqueue）：新来的人总是排在队尾。
  • 出队（Dequeue）：排在队首的人最先买到票并离开。

队列的这种 FIFO 特性完美地契合了 BFS 逐层搜索的需求。

  1. 我们将起始顶点放入队列中。
  2. 只要队列不为空，我们就从队首取出一个顶点（称之为当前顶点）。
  3. 我们访问这个当前顶点，并找到它所有尚未被访问过的邻居。
  4. 将这些新的邻居顶点全部放入队尾。
  5. 重复步骤 2-4。

通过这种方式，我们确保了先被发现的顶点（离源点更近的层）会先被处理，它们的邻居（更远的层）也就会被相应地、有次序地加入队列。这就实现了逐层扩展。

3.2 算法步骤详解

假设我们有一个图 G=(V,E)G=(V, E) 和一个起始顶点 ss。

  1. 初始化：

    • 创建一个队列 QQ。
    • 创建一个数组 dis[N] 来存储每个顶点到源点 ss 的距离，并将所有值初始化为一个特殊值（例如 −1-1 或无穷大），表示尚未访问。
    • 将源点 ss 的距离 dis[s] 设为 00。
    • 将源点 ss 入队 Q.push(s)Q.push(s)。

  2. 循环搜索：

    • 当队列 QQ 不为空时，执行以下操作： a. 从队首取出一个顶点 uu：u=Q.front()u = Q.front()，Q.pop()Q.pop()。 b. 遍历 uu 的所有邻居 vv： i. 如果 vv 尚未被访问（即 dis[v] == -1）： * 标记 vv 为已访问。 * 更新 vv 到源点的距离：dis[v] = dis[u] + 1。 * 将 vv 入队：Q.push(v)Q.push(v)。

  3. 结束：

    • 当队列为空时，搜索结束。此时，dis 数组中就包含了从源点 ss 到所有可达顶点的最短距离。如果某个顶点的 dis 值仍为初始的特殊值，则表示从 ss 无法到达该顶点。

3.3 伪代码

BFS(G, s):
  // G: 图, s: 起始顶点
  let Q be a queue
  let dis be an array to store distances, initialized to infinity
  
  dis[s] = 0
  Q.push(s)
  
  while Q is not empty:
    u = Q.front()
    Q.pop()
    
    for each neighbor v of u in G:
      if dis[v] is infinity: // 如果 v 未被访问
        dis[v] = dis[u] + 1
        Q.push(v)

四、BFS 示例：一步步走过迷宫

让我们通过一个具体的例子来模拟 BFS 的过程。

问题：给定一个 n×mn \times m 的迷宫，其中 . 代表通路，# 代表墙壁。给定一个起点 S 和一个终点 T，求从 S 到 T 的最短步数。每一步可以向上下左右四个方向移动。

这是一个典型的 BFS 应用场景，因为“最短步数”正对应了无权图中的最短路径。我们可以把整个迷宫看作一个图：

  • 顶点：每个 .、S、T 方格都是一个顶点。
  • 边：如果两个通路方格相邻（上下左右），则它们之间有一条无向边。

迷宫示例 (5x5):

S . . # .
. # . . .
. # . # .
. . . # T
# # . . .

BFS 过程:

  1. 初始化:

    • 创建一个队列 Q。
    • 创建一个二维数组 dis[5][5] 存储步数，全部初始化为 −1-1。
    • 起点 S 坐标为 (0,0)(0, 0)。设置 dis[0][0] = 0。
    • 将 S (即坐标 (0,0)(0,0)) 加入队列 Q。
    • Q 当前为: [(0,0)]

  2. 第 1 轮 (处理距离为 0 的层):

    • 队首元素 (0,0) 出队。
    • 寻找 (0,0) 的邻居：(0,1) 和 (1,0)。它们都未被访问过 (dis 值为 −1-1)。
    • 更新它们的距离：dis[0][1] = dis[0][0] + 1 = 1, dis[1][0] = dis[0][0] + 1 = 1。
    • 将 (0,1) 和 (1,0) 入队。
    • Q 当前为: [(0,1), (1,0)]

  3. 第 2 轮 (处理距离为 1 的层):

    • 队首元素 (0,1) 出队。
    • 寻找 (0,1) 的邻居：(0,0) (已访问), (0,2) (未访问)。
    • 更新 dis[0][2] = dis[0][1] + 1 = 2。将 (0,2) 入队。
    • Q 当前为: [(1,0), (0,2)]
    • 队首元素 (1,0) 出队。
    • 寻找 (1,0) 的邻居：(0,0) (已访问), (2,0) (未访问)。
    • 更新 dis[2][0] = dis[1][0] + 1 = 2。将 (2,0) 入队。
    • Q 当前为: [(0,2), (2,0)]

  4. 第 3 轮 (处理距离为 2 的层):

    • 队首元素 (0,2) 出队。
    • 邻居：(0,1) (已访问), (1,2) (未访问)。
    • 更新 dis[1][2] = dis[0][2] + 1 = 3。将 (1,2) 入队。
    • Q 当前为: [(2,0), (1,2)]
    • 队首元素 (2,0) 出队。
    • 邻居：(1,0) (已访问), (3,0) (未访问)。
    • 更新 dis[3][0] = dis[2][0] + 1 = 3。将 (3,0) 入队。
    • Q 当前为: [(1,2), (3,0)]

... 这个过程会一直持续下去。每一轮循环，都会处理完同一距离（同一层）的所有节点，然后再将下一层的节点入队。

距离矩阵 dis 的变化过程:

初始:

 0 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

处理完 S 后 (距离 1):

 0  1 -1 -1 -1
 1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

处理完距离 1 的节点后 (距离 2):

 0  1  2 -1 -1
 1 -1 -1 -1 -1
 2 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

最终，当 T (坐标 (3,4)) 被访问时，dis[3][4] 的值就是从 S 到 T 的最短步数。如果 BFS 结束后 dis[3][4] 仍然是 −1-1，则说明 S 无法到达 T。

五、C++ 代码实现

下面我们用 C++ 来实现一个经典的 BFS 问题：在图中找源点到其他所有点的最短路。

5.1 题意概括

给定一个 NN 个点 MM 条边的无向无权图，以及一个起始点 SS。求 SS 到图中所有点的最短距离。如果无法到达，则距离为 −1-1。

5.2 核心代码

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5; // 顶点数量上限
vector<int> g[N];    // 邻接表存图
int d[N];              // 存储距离，-1表示未访问
int n, m, s;           // 点数，边数，起点

void bfs() {
    memset(d, -1, sizeof(d)); // 初始化所有距离为-1

    queue<int> q; // 创建队列
    q.push(s);    // 起点入队
    d[s] = 0;     // 起点到自身的距离为0

    while (!q.empty()) {
        int u = q.front(); // 取出队头元素
        q.pop();

        // 遍历 u 的所有邻居
        for (int v : g[u]) {
            if (d[v] == -1) { // 如果邻居 v 未被访问
                d[v] = d[u] + 1; // 更新距离
                q.push(v);     // 将 v 入队
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> s; // 读入点数、边数、起点

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v); // 无向图，加两条边
        g[v].push_back(u);
    }

    bfs(); // 执行广度优先搜索

    for (int i = 1; i <= n; ++i) {
        cout << d[i] << (i == n ? "" : " "); // 输出结果
    }
    cout << endl;

    return 0;
}

5.3 代码解释

  • g[N]: 一个 vector 数组，g[u] 存储了所有与顶点 u 直接相连的顶点。这是邻接表的标准实现。
  • d[N]: distance 的缩写，用于存储起点 s 到每个顶点的最短距离。同时，它也兼具 visited 数组的功能：如果 d[i] == -1，说明顶点 i 尚未被访问。
  • bfs() 函数：
    • memset(d, -1, sizeof(d)): 这是一个高效的初始化技巧。memset 按字节填充，-1 的二进制表示所有位都是 1，所以 int 类型的 d[i] 会被正确地设置为 -1。
    • queue<int> q: C++ STL 提供的队列容器，完美支持 push（入队）、pop（出队）、front（取队头元素）和 empty（判空）操作。
    • while (!q.empty()): 循环的核心条件。只要队列中还有待处理的节点，搜索就继续。
    • for (int v : g[u]): C++11 的范围 for 循环，方便地遍历 u 的所有邻居 v。
    • if (d[v] == -1): 这是 BFS 的关键。只有当一个邻居从未被访问过时，我们才更新它的距离并将其入队。这保证了每个顶点只入队一次，避免了死循环和重复计算。

5.4 复杂度分析

  • 时间复杂度: O(N+M)O(N+M)

    • NN 是顶点数， MM 是边数。
    • 每个顶点最多入队一次、出队一次。这部分操作的总时间是 O(N)O(N)。
    • 在整个 BFS 过程中，当我们处理顶点 uu 时，我们会遍历它的所有邻居。对于整个图来说，每条边 (u,v)(u, v) 都只会被访问两次（一次在处理 uu 的邻居时，一次在处理 vv 的邻居时，这是针对无向图；有向图则是一次）。因此，遍历所有邻接表的总时间是 O(M)O(M)。
    • 综上，总时间复杂度为 O(N+M)O(N+M)。

  • 空间复杂度: O(N)O(N)

    • 邻接表 g 需要 O(N+M)O(N+M) 的空间。但在复杂度分析中，我们通常认为图的存储是输入的一部分，不计入额外空间。
    • 距离数组 d 需要 O(N)O(N) 的空间。
    • 队列 q 在最坏的情况下（例如一个星形图，一个中心点连接所有其他点），可能需要存储 N−1N-1 个顶点，因此空间复杂度是 O(N)O(N)。
    • 综上，额外的空间复杂度为 O(N)O(N)。

六、BFS 的典型应用

除了最基础的求最短路径，BFS 还有许多变体和应用。

6.1 走迷宫问题（二维/三维网格）

这是最经典的应用。如前所述，任何网格上的移动问题，只要每一步的“代价”相同，都可以转化为 BFS 问题。

  • 顶点：网格中的每个合法位置。
  • 边：从一个位置可以一步到达的另一个位置。

变化：

  • 带传送门的迷宫：如果从点 A 可以瞬间传送到点 B，这相当于在图中 A 和 B 之间增加了一条边。
  • 有多种移动方式的棋盘：例如，一个棋子可以走“日”字（像象棋的马），也可以直走。那么从一个点出发，它所有可能的下一步落点都是它的邻居。

6.2 连通块计数

在一个图中，如果从顶点 uu 可以到达顶点 vv，则称 uu 和 vv 是连通的。一个连通块是图的一个子图，其中任意两个顶点都相互连通。

问题：计算一个图中有多少个独立的连通块。

思路：

  1. 遍历所有顶点，从 11 到 NN。
  2. 如果当前顶点 ii 还没有被访问过，说明我们发现了一个新的连通块。
  3. 以 ii 为起点，执行一次 BFS。这次 BFS 会访问到所有与 ii 在同一个连通块内的顶点。
  4. 连通块计数器加一。
  5. 继续遍历，寻找下一个未被访问的顶点。
#include<bits/stdc++.h>
using namespace std;
// ... (图的存储和基本变量)

bool vis[N]; // 访问标记数组

void bfs(int s) { // 标准的BFS，但只访问连通的部分
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : g[u]){
            if(!vis[v]){
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    // ... (IO优化和图的输入)
    int cnt = 0; // 连通块计数器
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) { // 如果发现一个未被访问过的顶点
            bfs(i);      // 从它开始BFS，标记整个连通块
            cnt++;       // 计数器加一
        }
    }
    cout << cnt << endl;
    return 0;
}

6.3 树的层次遍历

树是一种特殊的图（无环连通图）。对树进行层次遍历（Level Order Traversal），即从上到下、从左到右逐层访问节点，其实现方法与 BFS 完全一致。

  • 从根节点开始 BFS。
  • dis 数组在这里可以用来记录每个节点的深度。dis[root] = 0。

6.4 拓扑排序（Kahn算法）

对于一个有向无环图（DAG），拓扑排序是其顶点的线性排序，使得对于每一条有向边 (u,v)(u, v)，顶点 uu 都排在顶点 vv 的前面。

Kahn 算法是实现拓扑排序的一种方法，它基于 BFS 的思想。

思路：

  1. 计算所有顶点的入度（指向该顶点的边的数量）。
  2. 将所有入度为 00 的顶点放入一个队列。这些是图的起点，可以作为排序的最前部分。
  3. 当队列不为空时： a. 取出一个顶点 uu。将 uu 加入拓扑序列的结果中。 b. 遍历 uu 的所有邻居 vv。 c. 将边 (u,v)(u, v)“删除”，即把 vv 的入度减 11。 d. 如果 vv 的入度变为 00，则将 vv 入队。
  4. 如果最终拓扑序列中的顶点数量等于图的顶点总数，则排序成功。否则，说明图中存在环。

这个过程与 BFS 非常相似，都是从一个初始集合（入度为0的节点）开始，逐层处理，并将满足新条件（入度变为0）的节点加入队列。

广度优先搜索是图论算法的基石之一。它的核心在于队列数据结构和逐层扩展的思想。

  • 适用场景：主要用于无权图，解决最短路径问题。
  • 核心数据结构：队列（Queue），保证先进先出（FIFO）。
  • 实现关键：一个记录距离/访问状态的数组（如 dis 或 vis），确保每个节点只被访问和入队一次。
  • 复杂度：时间 O(N+M)O(N+M)，空间 O(N)O(N)。
  • 思想：从源点出发，像水波一样，一层一层地向外探索。
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 陕ICP备2025061476号
  3. Worker 0, 112ms
  4. Powered Dong Dong