无向图的最短路径问题的 BFS 解法

字数 2140 2025-12-10 04:55:02

无向图的最短路径问题的 BFS 解法

我将为你讲解如何使用广度优先搜索（BFS）解决无向无权图上的单源最短路径问题。这个问题虽然基础，却是理解图遍历和最短路径算法的基石。

题目描述
给定一个无向无权连通图（可以是有权但所有权重相等，通常视为无权），以及一个指定的源顶点 s，要求找出从源顶点 s 到图中所有其他顶点的最短路径长度，并可能要求输出具体的路径。这里的“最短路径”定义为从起点到目标点所经过的边数最少的路径。

核心思想
在无权图中，每条边的“距离”或“代价”均为 1。广度优先搜索（BFS）按“层次”向外探索：首先访问所有距离为 1 的顶点，然后访问距离为 2 的顶点，依此类推。这恰好保证了当我们第一次访问某个顶点时，所走的路径就是从源点到该顶点的最短路径。

解题步骤

步骤 1：问题建模与数据结构

图的表示：通常使用邻接表，更节省空间且便于快速访问相邻顶点。
需要的数据结构：
- queue：一个先进先出（FIFO）队列，用于存放待访问的顶点。
- visited 数组/集合：记录顶点是否已被访问，避免重复访问。
- distance 数组：记录从源点 s 到每个顶点的最短距离。初始时，所有顶点的距离设为无穷大（或一个很大的数，如 INT_MAX），distance[s] = 0。
- parent 数组（可选）：记录在最短路径上，每个顶点的前驱顶点。用于最终回溯构造出具体路径。

步骤 2：初始化

将所有顶点的 visited 状态设为 false，distance 设为无穷大。
将源顶点 s 标记为已访问（visited[s] = true），距离设为 0（distance[s] = 0），并将其加入队列 queue。
如果需记录路径，将 parent[s] 设为 -1（表示没有前驱，是起点）。

步骤 3：BFS 遍历过程

当队列不为空时，执行循环：
a. 从队列头部取出一个顶点 u。
b. 遍历 u 的所有邻接顶点 v（即所有与 u 直接相连的顶点）。
c. 对于每个邻接顶点 v：
- 如果 v 尚未被访问过（visited[v] == false）：
- 标记 v 为已访问（visited[v] = true）。
- 设置 v 的距离为 distance[u] + 1。因为从 s 到 u 的距离已知为 distance[u]，而 u 到 v 有一条边，所以从 s 到 v 的最短距离就是 distance[u] + 1。
- 设置 v 的前驱为 u（parent[v] = u）。
- 将 v 加入队列尾部。
- 如果 v 已经被访问过，则忽略（因为 BFS 第一次访问 v 时已经找到了最短路径）。

步骤 4：终止与结果
当队列为空时，BFS 结束。此时：

distance 数组中存储的就是从源点 s 到所有顶点的最短距离。对于无法到达的顶点（如果图不连通），其距离值仍为初始的无穷大。
如果需要输出从 s 到某个顶点 t 的具体路径，可以通过 parent 数组从 t 开始不断回溯到 s，然后反转序列即可得到从 s 到 t 的路径。

为什么 BFS 能保证找到的是最短路径？
关键点在于 BFS 的 层次遍历 特性。设想从 s 出发，所有距离为 1 的顶点在第一轮被访问并记录距离；距离为 2 的顶点必须在第一轮某个顶点的邻居中，在第二轮被访问。由于我们是从队列（先进先出）中按顺序处理的，所以在第一次访问到某个顶点 v 时，我们走的路径必然是能到达 v 的、边数最少的路径。任何其他路径如果更短，那么 v 应该属于更早的层次，在之前就已经被访问了。

算法复杂度

时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。因为每个顶点和每条边都只被访问常数次。
空间复杂度：O(V)，用于队列、距离数组、访问标记等。

示例
考虑一个简单图：顶点为 {0, 1, 2, 3, 4}，边为 {(0,1), (0,2), (1,3), (2,4)}，源点为 0。

初始化：distance = [0, ∞, ∞, ∞, ∞]，队列 Q = [0]。
处理 0：邻居 1 和 2 未被访问，distance[1]=1，distance[2]=1，Q = [1, 2]。
处理 1：邻居 3 未被访问，distance[3]=2，Q = [2, 3]。
处理 2：邻居 4 未被访问，distance[4]=2，Q = [3, 4]。
处理 3：邻居都已访问或无邻居，Q = [4]。
处理 4：结束。
最终 distance = [0, 1, 1, 2, 2]，即为从顶点 0 到所有顶点的最短距离。

通过以上步骤，你可以清晰地理解并实现 BFS 求解无权图最短路径问题。它是许多更复杂图论算法（如 Dijkstra 在权值为 1 时的特例、网络流中的分层图构建等）的基础。

无向图的最短路径问题的 BFS 解法我将为你讲解如何使用广度优先搜索（BFS）解决无向无权图上的单源最短路径问题。这个问题虽然基础，却是理解图遍历和最短路径算法的基石。题目描述给定一个无向无权连通图（可以是有权但所有权重相等，通常视为无权），以及一个指定的源顶点 s ，要求找出从源顶点 s 到图中所有其他顶点的最短路径长度，并可能要求输出具体的路径。这里的“最短路径”定义为从起点到目标点所经过的边数最少的路径。核心思想在无权图中，每条边的“距离”或“代价”均为 1。广度优先搜索（BFS）按“层次”向外探索：首先访问所有距离为 1 的顶点，然后访问距离为 2 的顶点，依此类推。这恰好保证了当我们第一次访问某个顶点时，所走的路径就是从源点到该顶点的最短路径。解题步骤步骤 1：问题建模与数据结构图的表示：通常使用邻接表，更节省空间且便于快速访问相邻顶点。需要的数据结构： queue ：一个先进先出（FIFO）队列，用于存放待访问的顶点。 visited 数组/集合：记录顶点是否已被访问，避免重复访问。 distance 数组：记录从源点 s 到每个顶点的最短距离。初始时，所有顶点的距离设为无穷大（或一个很大的数，如 INT_MAX ）， distance[s] = 0 。 parent 数组（可选）：记录在最短路径上，每个顶点的前驱顶点。用于最终回溯构造出具体路径。步骤 2：初始化将所有顶点的 visited 状态设为 false ， distance 设为无穷大。将源顶点 s 标记为已访问（ visited[s] = true ），距离设为 0（ distance[s] = 0 ），并将其加入队列 queue 。如果需记录路径，将 parent[s] 设为 -1 （表示没有前驱，是起点）。步骤 3：BFS 遍历过程当队列不为空时，执行循环： a. 从队列头部取出一个顶点 u 。 b. 遍历 u 的所有邻接顶点 v （即所有与 u 直接相连的顶点）。 c. 对于每个邻接顶点 v ： - 如果 v 尚未被访问过（ visited[v] == false ）： - 标记 v 为已访问（ visited[v] = true ）。 - 设置 v 的距离为 distance[u] + 1 。因为从 s 到 u 的距离已知为 distance[u] ，而 u 到 v 有一条边，所以从 s 到 v 的最短距离就是 distance[u] + 1 。 - 设置 v 的前驱为 u （ parent[v] = u ）。 - 将 v 加入队列尾部。 - 如果 v 已经被访问过，则忽略（因为 BFS 第一次访问 v 时已经找到了最短路径）。步骤 4：终止与结果当队列为空时，BFS 结束。此时： distance 数组中存储的就是从源点 s 到所有顶点的最短距离。对于无法到达的顶点（如果图不连通），其距离值仍为初始的无穷大。如果需要输出从 s 到某个顶点 t 的具体路径，可以通过 parent 数组从 t 开始不断回溯到 s ，然后反转序列即可得到从 s 到 t 的路径。为什么 BFS 能保证找到的是最短路径？关键点在于 BFS 的层次遍历特性。设想从 s 出发，所有距离为 1 的顶点在第一轮被访问并记录距离；距离为 2 的顶点必须在第一轮某个顶点的邻居中，在第二轮被访问。由于我们是从队列（先进先出）中按顺序处理的，所以在第一次访问到某个顶点 v 时，我们走的路径必然是能到达 v 的、边数最少的路径。任何其他路径如果更短，那么 v 应该属于更早的层次，在之前就已经被访问了。算法复杂度时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。因为每个顶点和每条边都只被访问常数次。空间复杂度：O(V)，用于队列、距离数组、访问标记等。示例考虑一个简单图：顶点为 {0, 1, 2, 3, 4}，边为 {(0,1), (0,2), (1,3), (2,4)}，源点为 0。初始化： distance = [0, ∞, ∞, ∞, ∞] ，队列 Q = [ 0 ]。处理 0：邻居 1 和 2 未被访问， distance[1]=1 ， distance[2]=1 ，Q = [ 1, 2 ]。处理 1：邻居 3 未被访问， distance[3]=2 ，Q = [ 2, 3 ]。处理 2：邻居 4 未被访问， distance[4]=2 ，Q = [ 3, 4 ]。处理 3：邻居都已访问或无邻居，Q = [ 4 ]。处理 4：结束。最终 distance = [0, 1, 1, 2, 2] ，即为从顶点 0 到所有顶点的最短距离。通过以上步骤，你可以清晰地理解并实现 BFS 求解无权图最短路径问题。它是许多更复杂图论算法（如 Dijkstra 在权值为 1 时的特例、网络流中的分层图构建等）的基础。