一、引言

想象一下，你置身于一个巨大而复杂的迷宫之中。四周的墙壁高耸，通道错综复杂，每一个转角都可能通向死胡同，也可能是通往出口的正确道路。你站在迷宫的起点，目标只有一个：尽快找到出口，走出这个迷宫。此时，你会如何规划自己的路线呢？是随意选择一条通道前行，直到碰壁再折返？还是有一种更科学、更高效的方法来探索这个迷宫呢？

在计算机科学的世界里，类似的问题层出不穷。而宽度优先搜索（Breadth – First Search，简称 BFS），就是一种用于解决这类问题的强大算法工具。它如同一位经验丰富的探险家，有条不紊地探索着迷宫的每一个角落，从起点开始，一层一层地向外扩展，直到找到目标。

在这篇文章中，我们将深入探索 C++ 中的宽度优先搜索算法。无论你是一名对算法充满好奇的编程新手，还是渴望提升算法技能的进阶开发者，都能在这里找到有价值的内容。接下来，让我们一起揭开宽度优先搜索的神秘面纱，看看它是如何在代码的世界里解决各种复杂问题的。

二、什么是宽度优先搜索（BFS）

2.1 概念介绍

宽度优先搜索（BFS）是一种用于图或树的遍历算法。它从给定的起始节点开始，以一种逐层扩展的方式来探索图或树的节点。就像是在平静的湖面投入一颗石子，激起的涟漪会以石子落点为中心，一圈一圈地向外扩散。BFS 从起始节点出发，先访问与起始节点直接相连的所有节点（这是第一层），然后再依次访问与这些节点直接相连的未访问过的节点（第二层），以此类推，直到遍历完所有可达节点，或者找到目标节点。在遍历过程中，BFS 通常使用队列（Queue）来存储待访问的节点，这是 BFS 实现的关键数据结构，保证了节点按照 “宽度” 顺序被访问 。

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

深度优先搜索（DFS）和 BFS 一样，也是一种用于遍历图或树的算法，但它们在遍历顺序和特点上有明显的区别。

DFS 就像是一个探险家，一旦选择了一条路径，就会沿着这条路径尽可能深入地探索，直到无法继续（比如到达叶子节点或死胡同），然后再回溯到上一个节点，尝试其他未探索的路径。它使用的典型数据结构是栈（Stack），也可以通过递归实现。例如在遍历一个树形结构时，DFS 会先遍历根节点的一个子节点，然后一直深入这个子节点的子树，直到最底层的叶子节点，再回溯到上一层。

而 BFS 则更像是在绘制地图，从起点开始，一层一层地向外扩展，先探索完距离起点较近的所有区域，再逐渐向外延伸。

从找到目标节点的角度来看，如果目标节点距离起始节点较近，BFS 更有可能快速找到目标，因为它优先遍历距离近的节点，能更快地覆盖到目标节点所在的区域，且找到的路径通常是最短路径（如果所有边的权重相同）。DFS 则可能在深入探索其他分支时，花费较长时间才找到目标节点，找到的路径不一定是最短路径。

在空间复杂度方面，DFS 由于只需要保存当前路径上的节点，所以在树或图的深度较大时，空间占用相对较小。而 BFS 需要保存每一层的所有节点，对于宽度较大的图或树，空间需求会显著增加。

三、BFS 的工作原理

3.1 核心步骤详解

1. 初始化：

• • 首先，创建一个队列（Queue）用于存储待访问的节点。
• • 定义一个标记数组（例如visited数组），用于记录每个节点是否已经被访问过，初始时所有节点都标记为未访问。
• • 将起始节点放入队列中，并标记为已访问。这是 BFS 遍历的起点，就像在迷宫中确定了出发点 。

1. 循环遍历：

• • 当队列不为空时，进入循环。这是 BFS 的核心循环部分，只要还有节点等待访问，就继续遍历。
• • 从队列中取出队首节点，这个节点是当前要访问和处理的节点。比如在迷宫例子中，就是当前所在的位置 。
• • 检查该节点是否为目标节点。如果是，说明已经找到了目标，BFS 可以结束。例如在迷宫中找到了出口 。
• • 如果不是目标节点，遍历该节点的所有相邻节点。对于图中的节点，相邻节点就是与它直接相连的节点；对于迷宫中的格子，相邻格子就是上下左右四个方向可到达的格子。
• • 对于每个未被访问过的相邻节点，将其标记为已访问，并放入队列的尾部。这一步保证了下一轮会访问这些相邻节点，就像在迷宫中探索周围未走过的通道 。

1. 结束条件：

• • 当队列为空时，说明所有可达节点都已经被访问过了。如果此时还没有找到目标节点，那么表示从起始节点无法到达目标节点 。

3.2 示例展示

为了更直观地理解 BFS 的工作过程，我们来看一个简单的无向图示例。假设有如下一个图，节点编号从 0 到 4 ：

0

/ \

1 2

/ \ \

3 4 3

我们从节点 0 开始进行 BFS 遍历，具体步骤如下：

1. 初始化：

• • 队列q = [0]，visited = [true, false, false, false, false]。此时队列中只有起始节点 0，并且标记 0 已经被访问 。

1. 第一轮循环：

• • 取出队首节点 0，访问它。然后遍历 0 的相邻节点 1 和 2 。
• • 节点 1 未被访问，标记为已访问并放入队列，此时队列q = [1]，visited = [true, true, false, false, false]。
• • 节点 2 未被访问，标记为已访问并放入队列，此时队列q = [1, 2]，visited = [true, true, true, false, false]。

1. 第二轮循环：

• • 取出队首节点 1，访问它。然后遍历 1 的相邻节点 0、3 和 4 。
• • 节点 0 已被访问，跳过。
• • 节点 3 未被访问，标记为已访问并放入队列，此时队列q = [2, 3]，visited = [true, true, true, true, false]。
• • 节点 4 未被访问，标记为已访问并放入队列，此时队列q = [2, 3, 4]，visited = [true, true, true, true, true]。

1. 第三轮循环：

• • 取出队首节点 2，访问它。然后遍历 2 的相邻节点 0 和 3 。
• • 节点 0 已被访问，跳过。
• • 节点 3 已被访问，跳过。此时队列q = [3, 4]。

1. 第四轮循环：

• • 取出队首节点 3，访问它。然后遍历 3 的相邻节点 1 和 2 。
• • 节点 1 和 2 都已被访问，跳过。此时队列q = [4]。

1. 第五轮循环：

• • 取出队首节点 4，访问它。然后遍历 4 的相邻节点 1 。
• • 节点 1 已被访问，跳过。此时队列q = []，队列为空，BFS 结束 。

最终的遍历顺序为 0, 1, 2, 3, 4，通过这个过程可以清晰地看到 BFS 是如何一层一层地遍历图中的节点的。

四、C++ 中 BFS 的实现

4.1 所需数据结构

1. 队列（Queue）：

• • 在 C++ 中，std::queue是实现 BFS 的关键数据结构。它遵循先进先出（FIFO）的原则，这正好符合 BFS 逐层扩展的特点。在 BFS 遍历过程中，我们将待访问的节点放入队列中，每次从队列头部取出一个节点进行访问，然后将其未访问过的相邻节点添加到队列尾部。例如，在迷宫问题中，我们可以把当前所在的格子作为节点，从起点开始，将起点放入队列，然后在每次循环中取出队首的格子，检查它的上下左右四个相邻格子是否可以走，如果可以走且未被访问过，就将这些相邻格子放入队列 。

1. 标记数组（Visited Array）：

• • 通常使用一个布尔类型的数组来标记每个节点是否已经被访问过。例如，对于一个包含n个节点的图，可以定义一个bool visited[n]数组，初始时将所有元素设置为false，表示所有节点都未被访问。当访问一个节点时，将对应的visited数组元素设置为true，这样在后续遍历中，如果遇到已经被标记为true的节点，就可以跳过，避免重复访问，从而提高算法效率。在迷宫例子中，标记数组可以用来记录哪些格子已经走过，防止在迷宫中反复走同一个地方 。

1. 图的存储结构：

• • 邻接矩阵（Adjacency Matrix）：对于一个具有n个节点的图，可以使用一个n * n的二维数组adjMatrix来表示。如果节点i和节点j之间有边相连，那么adjMatrix[i][j]和adjMatrix[j][i]（对于无向图）的值为1或边的权重（对于带权图），否则为0。邻接矩阵的优点是直观，易于理解和实现，能够快速判断两个节点之间是否有边相连。但缺点是空间复杂度较高，对于稀疏图（边数远小于节点数的平方）会浪费大量空间 。
• • 邻接表（Adjacency List）：在 C++ 中，可以使用std::vector来实现邻接表。对于每个节点i，用一个std::vector来存储与它相邻的节点。例如，std::vector<int> adjList[n]，其中adjList[i]存储了节点i的所有相邻节点。邻接表的空间复杂度较低，适用于稀疏图，并且在遍历图时可以方便地访问每个节点的相邻节点。

4.2 代码实现

1. 使用邻接矩阵表示图的 BFS 代码示例：

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

void BFS(const vector<vector<int>>& adjMatrix, int start) {

int n = adjMatrix.size();

vector<bool> visited(n, false);

queue<int> q;

visited[start] = true;

q.push(start);

while (!q.empty()) {

int current = q.front();

q.pop();

cout << current << " ";

for (int i = 0; i < n; ++i) {

if (adjMatrix[current][i] &&!visited[i]) {

visited[i] = true;

q.push(i);

}

}

}

}

int main() {

// 示例邻接矩阵，这里假设是一个无向图

vector<vector<int>> adjMatrix = {

{0, 1, 1, 0, 0},

{1, 0, 1, 1, 0},

{1, 1, 0, 0, 1},

{0, 1, 0, 0, 0},

{0, 0, 1, 0, 0}

};

cout << "从节点0开始的BFS遍历结果: ";

BFS(adjMatrix, 0);

return 0;

}

代码解释：

• 首先定义了BFS函数，它接受邻接矩阵adjMatrix和起始节点start作为参数。
• 创建一个大小为n（节点数）的布尔型visited数组，用于标记节点是否被访问，初始值都为false。
• 创建一个队列q，用于存储待访问的节点。
• 将起始节点start标记为已访问，并放入队列。
• 在while循环中，当队列不为空时，取出队首节点current，输出该节点。
• 遍历current节点的所有邻接节点（通过邻接矩阵判断），如果邻接节点未被访问且与current节点有边相连（adjMatrix[current][i]为真），则将其标记为已访问并放入队列 。

1. 使用邻接表表示图的 BFS 代码示例：

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

void BFS(const vector<vector<int>>& adjList, int start) {

int n = adjList.size();

vector<bool> visited(n, false);

queue<int> q;

visited[start] = true;

q.push(start);

while (!q.empty()) {

int current = q.front();

q.pop();

cout << current << " ";

for (int neighbor : adjList[current]) {

if (!visited[neighbor]) {

visited[neighbor] = true;

q.push(neighbor);

}

}

}

}

int main() {

// 示例邻接表，这里假设是一个无向图

vector<vector<int>> adjList = {

{1, 2},

{0, 2, 3},

{0, 1, 4},

{1, 5},

{2},

{3}

};

cout << "从节点0开始的BFS遍历结果: ";

BFS(adjList, 0);

return 0;

}

代码解释：

• BFS函数接受邻接表adjList和起始节点start作为参数。
• 同样创建visited数组和队列q。
• 将起始节点标记为已访问并放入队列。
• 在while循环中，取出队首节点current并输出。
• 通过遍历adjList[current]，即当前节点current的邻接表，获取其所有相邻节点neighbor，如果neighbor未被访问过，则将其标记为已访问并放入队列 。

4.3 代码优化技巧

1. 减少不必要的计算：

• • 在判断节点是否可达时，避免重复计算。例如，在一个迷宫问题中，如果已经计算过某个格子到终点的距离，并且这个距离不会改变（比如迷宫布局固定），可以将这个结果缓存起来，下次需要时直接读取，而不是重新计算。可以使用一个全局数组或者哈希表来存储这些已经计算过的结果。
• • 在图的遍历中，如果某些节点在特定条件下肯定不会被访问到，可以提前进行判断并跳过相关计算。比如在一个有向无环图（DAG）中，如果某个节点的入度为 0 且不是起始节点，那么在从特定起始节点开始的 BFS 中，这个节点肯定不会被访问到，可以直接忽略对它的处理 。

1. 合理使用数据结构：

• • 对于稀疏图，优先使用邻接表而不是邻接矩阵来存储图结构，以减少空间占用和提高遍历效率。因为邻接表只存储实际存在的边，而邻接矩阵对于稀疏图会有大量的 0 元素，浪费空间且在遍历查找边时效率较低。
• • 在某些情况下，可以使用双端队列（std::deque）代替普通队列（std::queue）。例如，在双向 BFS（从起点和终点同时进行 BFS）中，双端队列可以方便地在两端进行插入和删除操作，优化算法的实现和性能 。

1. 剪枝策略：

• • 在搜索过程中，根据问题的特性制定剪枝策略，减少不必要的搜索分支。比如在一个求解最短路径的问题中，如果当前路径长度已经超过了已知的最短路径长度，那么可以直接停止对这个路径的扩展，从而减少搜索空间，提高算法效率 。

五、BFS 的应用场景

5.1 最短路径问题

在现实生活中，地图导航是我们经常使用的工具。当我们在地图上输入出发地和目的地后，导航系统会迅速规划出一条最优路线，而这个最优路线往往就是最短路径（在不考虑路况等复杂因素，仅考虑距离的情况下）。BFS 在解决这类最短路径问题中发挥着重要作用 。

以一个简单的城市地图为例，城市中的各个路口可以看作是图的节点，连接路口的道路就是边。假设我们要从城市的 A 点到达 B 点，使用 BFS 算法时，从 A 点开始，将与 A 点直接相连的所有路口加入队列，标记这些路口为已访问。然后从队列中取出一个路口，检查它是否是 B 点，如果是则找到了路径；如果不是，将该路口未访问过的相邻路口加入队列。这样一层一层地扩展，由于 BFS 是按层次遍历的，所以当第一次到达 B 点时，所经过的路径就是从 A 点到 B 点的最短路径（前提是所有道路的长度相同，即边权相同 ）。

在实际的地图导航系统中，可能会涉及到更复杂的情况，比如不同道路的通行时间不同（即边权不同），此时单纯的 BFS 不能直接得到最短路径，但 BFS 的思想依然是基础，像 Dijkstra 算法等就是在 BFS 思想基础上，结合优先队列等数据结构来处理边权不同的情况，从而找到真正的最短路径 。

5.2 图的连通性判断

判断图中节点的连通性是图论中的一个基本问题。在实际场景中，比如通信网络中，我们需要知道各个节点（设备）之间是否能够连通，以确保信息能够正常传输。BFS 可以有效地解决这个问题 。

对于一个给定的图，从任意一个节点开始进行 BFS 遍历。在遍历过程中，所有能够被访问到的节点都与起始节点是连通的。当 BFS 结束后，如果图中所有节点都被访问过，那么说明这个图是连通图，即任意两个节点之间都存在路径相连；如果存在未被访问的节点，那么这个图就是非连通图，未被访问的节点与起始节点所在的连通分量是相互独立的 。

例如，在一个社交网络中，每个用户是一个节点，用户之间的好友关系是边。我们可以选择一个用户作为起始点，通过 BFS 遍历，就可以找出与这个用户直接或间接相连的所有用户，从而判断出这个社交网络中不同用户群体之间的连通性 。

5.3 状态空间搜索

以八数码问题为例，在一个 3×3 的棋盘上，有 1 – 8 这 8 个数字和一个空格，目标是通过移动空格，将初始状态的数字排列变成目标状态（例如 12345678 按顺序排列 ）。每一次移动空格都可以看作是状态的转换，整个问题就可以看作是在状态空间中搜索从初始状态到目标状态的路径 。

使用 BFS 来解决八数码问题时，将初始状态作为起始节点放入队列，同时记录已访问过的状态（防止重复搜索同一个状态，陷入死循环 ）。每次从队列中取出一个状态，检查它是否是目标状态。如果是，则找到了从初始状态到目标状态的最短移动序列（因为 BFS 找到的路径是最短的）；如果不是，生成该状态下所有可能的移动（空格上、下、左、右移动产生的新状态 ），将这些新状态中未被访问过的加入队列。通过这样不断地扩展状态，直到找到目标状态或者队列为空（表示无法从初始状态到达目标状态 ）。在这个过程中，BFS 就像在状态空间的迷宫中，一层一层地寻找出口（目标状态 ），确保找到的路径是最短的，也就是最少的移动步数 。

六、常见问题与解决方法

6.1 内存溢出

在 BFS 中，内存溢出通常是由于队列过大导致的。当搜索空间非常大，且没有有效的剪枝策略时，队列中会不断积累大量的节点，从而消耗过多的内存 。

例如，在一个非常大的迷宫中进行 BFS 搜索，迷宫的每个格子都可能作为节点加入队列。如果迷宫规模巨大，且没有对已经访问过的节点进行有效的标记和过滤，那么队列会随着搜索的进行不断膨胀，最终导致内存溢出 。

解决方法如下：

1. 优化标记数组：确保标记数组能够准确记录已经访问过的节点，避免重复访问。例如，在一个二维迷宫中，可以使用一个二维布尔数组visited[i][j]来标记坐标为(i, j)的格子是否被访问过。这样在将新节点加入队列之前，先检查其是否已经被标记，若已标记则不加入队列，从而减少队列中的节点数量 。
2. 合理设置搜索边界：在某些问题中，可以根据问题的特点设置搜索边界。比如在一个求最短路径的问题中，如果已知目标节点一定在某个半径范围内，那么可以在搜索到超出这个半径的节点时，直接丢弃，不再将其加入队列，从而控制队列的大小 。
3. 使用哈希表代替数组标记：当节点的编号不是连续的，或者搜索空间的维度非常大时，使用数组标记可能会浪费大量空间，并且无法准确标记所有节点。此时可以使用哈希表来记录已经访问过的节点。哈希表可以更灵活地存储和查找节点，避免因数组索引范围过大导致的内存浪费和标记不准确问题 。

6.2 效率低下

BFS 效率低下的情况通常出现在搜索范围过大时。当图或树的规模很大，且目标节点距离起始节点较远时，BFS 需要遍历大量的节点，导致时间和空间复杂度增加 。

例如，在一个社交网络中，如果要从一个用户开始，通过 BFS 找到与他有一定关系（比如好友的好友的好友）的所有用户，随着搜索层数的增加，需要访问的节点数量会呈指数级增长，使得搜索效率变得非常低 。

优化策略如下：

1. 双向 BFS：从起始节点和目标节点同时进行 BFS 搜索，当两个搜索的结果相遇时，就找到了最短路径。这种方法可以显著减少搜索的空间和时间复杂度。例如，在一个寻找从城市 A 到城市 B 最短路径的问题中，同时从城市 A 和城市 B 开始进行 BFS，当两个搜索在中间某个城市相遇时，就找到了从 A 到 B 的最短路径，相比从 A 单向搜索到 B，大大减少了搜索的节点数量 。
2. 启发式搜索：结合启发式函数，如 A算法，在 BFS 的基础上，根据节点到目标节点的估计距离来优先扩展更有可能接近目标的节点，从而提高搜索效率。例如，在一个地图导航应用中，使用 A算法，通过估计当前位置到目的地的直线距离（启发式函数），优先选择距离目的地更近的道路进行搜索，能够更快地找到最优路径 。
3. 剪枝优化：根据问题的性质，制定剪枝策略，在搜索过程中剪掉不可能到达目标的分支。比如在一个求解最优解的问题中，如果当前节点的解已经比已知的最优解更差，那么可以停止对这个节点的扩展，减少不必要的搜索，提高效率 。

七、总结与展望

宽度优先搜索作为一种基础且强大的算法，在图论、路径规划、状态空间搜索等众多领域都有着广泛的应用。通过本文，我们详细了解了 BFS 的概念、工作原理，掌握了在 C++ 中使用队列和标记数组等数据结构实现 BFS 的方法，还探讨了其在最短路径、图的连通性判断等实际场景中的应用，以及应对内存溢出和效率低下等常见问题的解决策略 。

BFS 的优势在于其按层次遍历的特性，能够高效地找到最短路径，并且在处理一些需要逐层探索的问题时表现出色。然而，BFS 也有其局限性，例如在搜索空间过大时，可能会面临内存和时间效率的挑战 。

展望未来，随着计算机技术的不断发展，算法应用的场景越来越复杂和多样化。希望读者在掌握 BFS 的基础上，能够深入学习和探索 BFS 在更多领域的应用，比如在人工智能、大数据分析、网络通信等前沿领域，BFS 与其他算法的结合也可能会产生新的解决方案 。同时，不断优化 BFS 的实现，提高其在大规模数据和复杂问题上的处理能力，将为解决实际问题带来更多的可能性。愿大家在算法的世界里不断探索，收获更多的知识和乐趣。 ​