图论中的广度优先搜索（BFS）算法

字数 1387 2025-11-04 08:32:42

图论中的广度优先搜索（BFS）算法

题目描述
给定一个无向图（或有向图）和一个起始顶点 \(s\)，要求使用广度优先搜索（BFS）算法遍历图，并计算从 \(s\) 到所有其他顶点的最短路径（假设边权均为 1）。BFS 的核心思想是按“层次”逐层访问顶点，确保先访问距离 \(s\) 最近的顶点。

解题过程

1. 算法核心思想
BFS 通过队列（FIFO 结构）实现层次遍历。从起点 \(s\) 开始，先访问所有与 \(s\) 直接相邻的顶点（第一层），再访问这些顶点的未访问邻居（第二层），依此类推。由于每次扩展都是当前层的最短距离，BFS 天然适用于无权图的最短路径计算。

2. 数据结构准备

队列（Queue）：存储待访问的顶点。
距离数组（dist）：记录每个顶点到起点 \(s\) 的距离，初始时设为无穷大（表示未访问）。
父节点数组（parent）：记录最短路径树上每个顶点的前驱节点，用于重构路径（可选）。

3. 算法步骤

初始化：
- 将起点 \(s\) 的距离设为 0（dist[s] = 0），并将其加入队列。
- 其他顶点的距离初始化为无穷大（或 -1）。
循环处理队列：
- 从队列中取出队首顶点 \(u\)。
- 遍历 \(u\) 的所有邻居 \(v\)：
  - 若 \(v\) 未被访问（即 dist[v] 为无穷大），则：
    - 设置 dist[v] = dist[u] + 1。
    - 记录 \(v\) 的父节点为 \(u\)（可选）。
    - 将 \(v\) 加入队列。
终止条件：队列为空时，所有从 \(s\) 可达的顶点均被访问完毕。

4. 实例演示
考虑以下无向图（顶点编号 0~4，边权为 1）：

0 — 1 — 2
|    |    |
3 — 4 — 5

起点 \(s = 0\)。

逐步执行：

初始：队列 = [0], dist[0] = 0，其他 dist 为 ∞。
处理顶点 0：
- 邻居 {1, 3} 均未访问，更新 dist[1] = 1, dist[3] = 1，父节点为 0，队列变为 [1, 3]。
处理顶点 1：
- 邻居 {0, 2, 4} 中，0 已访问，2 和 4 未访问，更新 dist[2] = 2, dist[4] = 2，队列变为 [3, 2, 4]。
处理顶点 3：
- 邻居 {0, 4} 中，0 已访问，4 未访问但已在前一步被访问（dist[4] 已更新），故跳过。
处理顶点 2：
- 邻居 {1, 5} 中，1 已访问，5 未访问，更新 dist[5] = 3，队列变为 [4, 5]。
处理顶点 4：
- 邻居 {1, 3, 5} 均已访问（dist[5] 已在顶点 2 处理时更新），无操作。
处理顶点 5：无未访问邻居。
结束：队列为空，最终 dist = [0, 1, 2, 1, 2, 3]。

5. 关键点说明

时间复杂度：\(O(V + E)\)，每个顶点和边仅处理一次。
空间复杂度：\(O(V)\)，用于存储队列和距离数组。
适用场景：无权图的最短路径、连通性检测、层次遍历等。
注意：若边权非 1，BFS 不保证最短路径（需改用 Dijkstra 算法）。

通过以上步骤，BFS 以层次顺序遍历图，并高效计算出最短路径。

图论中的广度优先搜索（BFS）算法题目描述给定一个无向图（或有向图）和一个起始顶点 \( s \)，要求使用广度优先搜索（BFS）算法遍历图，并计算从 \( s \) 到所有其他顶点的最短路径（假设边权均为 1）。BFS 的核心思想是按“层次”逐层访问顶点，确保先访问距离 \( s \) 最近的顶点。解题过程 1. 算法核心思想 BFS 通过队列（FIFO 结构）实现层次遍历。从起点 \( s \) 开始，先访问所有与 \( s \) 直接相邻的顶点（第一层），再访问这些顶点的未访问邻居（第二层），依此类推。由于每次扩展都是当前层的最短距离，BFS 天然适用于无权图的最短路径计算。 2. 数据结构准备队列（Queue）：存储待访问的顶点。距离数组（dist）：记录每个顶点到起点 \( s \) 的距离，初始时设为无穷大（表示未访问）。父节点数组（parent）：记录最短路径树上每个顶点的前驱节点，用于重构路径（可选）。 3. 算法步骤初始化：将起点 \( s \) 的距离设为 0（ dist[s] = 0 ），并将其加入队列。其他顶点的距离初始化为无穷大（或 -1）。循环处理队列：从队列中取出队首顶点 \( u \)。遍历 \( u \) 的所有邻居 \( v \)：若 \( v \) 未被访问（即 dist[v] 为无穷大），则：设置 dist[v] = dist[u] + 1 。记录 \( v \) 的父节点为 \( u \)（可选）。将 \( v \) 加入队列。终止条件：队列为空时，所有从 \( s \) 可达的顶点均被访问完毕。 4. 实例演示考虑以下无向图（顶点编号 0~4，边权为 1）：起点 \( s = 0 \)。逐步执行：初始：队列 = [ 0], dist[ 0 ] = 0，其他 dist 为 ∞。处理顶点 0 ：邻居 {1, 3} 均未访问，更新 dist[ 1] = 1, dist[ 3] = 1，父节点为 0，队列变为 [ 1, 3 ]。处理顶点 1 ：邻居 {0, 2, 4} 中，0 已访问，2 和 4 未访问，更新 dist[ 2] = 2, dist[ 4] = 2，队列变为 [ 3, 2, 4 ]。处理顶点 3 ：邻居 {0, 4} 中，0 已访问，4 未访问但已在前一步被访问（dist[ 4 ] 已更新），故跳过。处理顶点 2 ：邻居 {1, 5} 中，1 已访问，5 未访问，更新 dist[ 5] = 3，队列变为 [ 4, 5 ]。处理顶点 4 ：邻居 {1, 3, 5} 均已访问（dist[ 5 ] 已在顶点 2 处理时更新），无操作。处理顶点 5 ：无未访问邻居。结束：队列为空，最终 dist = [ 0, 1, 2, 1, 2, 3 ]。 5. 关键点说明时间复杂度：\( O(V + E) \)，每个顶点和边仅处理一次。空间复杂度：\( O(V) \)，用于存储队列和距离数组。适用场景：无权图的最短路径、连通性检测、层次遍历等。注意：若边权非 1，BFS 不保证最短路径（需改用 Dijkstra 算法）。通过以上步骤，BFS 以层次顺序遍历图，并高效计算出最短路径。