一、课上练习

编程练习

1. 最短路径: L3351

二、知识总结

✨ 核心思想

图的广度优先遍历（Breadth-First Search, BFS）是一种遍历或搜索图和树的算法。它从一个选定的源节点开始，探索所有邻近的节点，然后再从这些节点出发，探索它们的邻近节点，依此类推，直到访问了图中的所有可达节点。广度优先搜索在解决最短路径问题和连通性问题中非常有用，因为它从源节点开始逐层向外扩展。

✨ 广度优先遍历的特点

• 层次遍历：BFS 一层层地访问节点，首先访问距离源节点一条边的所有节点，然后是两条边的距离，依此类推。
• 使用队列：BFS 使用队列来管理待探索的节点，保证了节点是按照它们被发现的顺序被处理。
• 适用性：广泛应用于无权图中查找最短路径，因为第一次访问到任何节点的路径是从源点出发的最短路径。

✨ 算法原理

BFS 的基本步骤如下：

1. 初始化：创建一个队列 Q，一个布尔型数组 visited 来标记所有的节点最初都未被访问。
2. 开始节点：选择一个源节点，将其标记为已访问，然后将其加入队列 Q。
3. 处理队列中的节点：
   • 从 Q 中弹出一个节点 v。
   • 访问 v 的所有未被访问的邻接节点，将它们标记为已访问并入队。
4. 重复：重复步骤 3，直到队列为空。

下面的代码演示了图的广度优先遍历的实现方式：

1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6class Graph {
7    int V; // 图的顶点数
8    vector<int> *adj; // 邻接表
9public:
10    Graph(int V); // 构造函数
11    void addEdge(int v, int w); // 添加边
12    void BFS(int s); // 从顶点 s 执行 BFS
13};
14
15Graph::Graph(int V) {
16    this->V = V;
17    adj = new vector<int>[V];
18}
19
20void Graph::addEdge(int v, int w) {
21    adj[v].push_back(w); // 将 w 添加到 v 的列表中
22}
23
24void Graph::BFS(int s) {
25    vector<bool> visited(V, false); // 标记所有的顶点为未访问
26    queue<int> queue; // 创建一个队列用于 BFS
27
28    // 标记源节点为已访问并入队
29    visited[s] = true;
30    queue.push(s);
31
32    while (!queue.empty()) {
33        // 弹出一个顶点并打印
34        s = queue.front();
35        cout << s << " ";
36        queue.pop();
37
38        // 获取所有相邻的顶点
39        for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
40            if (!visited[*i]) {
41                visited[*i] = true;
42                queue.push(*i);
43            }
44        }
45    }
46}
47
48int main() {
49    Graph g(4);
50    g.addEdge(0, 1);
51    g.addEdge(0, 2);
52    g.addEdge(1, 2);
53    g.addEdge(2, 0);
54    g.addEdge(2, 3);
55    g.addEdge(3, 3);
56
57    cout << "Following is Breadth First Traversal (starting from vertex 2) \n";
58    g.BFS(2);
59
60    return 0;
61}

✨ 应用场景

• 最短路径：在无权图中找到从源点到其他所有顶点的最短路径。
• 社交网络：在社交网络中找到"六度分隔"现象，即任何两个人之间通过若干个朋友可在六步或更少步骤内相连。
• 网络爬虫：搜索引擎中用于网页爬取。
• 广播：在网络中有效地广播消息。
• 连通性：检查无向图的连通性或寻找所有连通分量。

广度优先搜索是图论中非常基础且强大的算法，能够解决多种与路径和连通性相关的问题。

✨ 执行示例

下面用一个具体的图，完整展示 BFS 的逐步执行过程。

示例图（无向图）： 6 个顶点

0 --- 1
|     |
2     3
|   / |
4 --- 5

邻接表：

• 0: [1, 2]
• 1: [0, 3]
• 2: [0, 4]
• 3: [1, 4, 5]
• 4: [2, 3, 5]
• 5: [3, 4]

从顶点 0 开始 BFS：

BFS 遍历结果：0 1 2 3 4 5

观察 BFS 的层次结构：

• 第 0 层（距离 0）：{0}
• 第 1 层（距离 1）：{1, 2}（0 的直接邻居）
• 第 2 层（距离 2）：{3, 4}（距离 0 为 2 条边）
• 第 3 层（距离 3）：{5}（距离 0 为 3 条边）

BFS 天然按照距离从近到远的顺序访问节点，这就是它能求最短路径的原因。

最短路径记录： 在 BFS 过程中，用 dist 数组记录每个节点到起点的距离：

dist[0]=0, dist[1]=1, dist[2]=1, dist[3]=2, dist[4]=2, dist[5]=3

顶点 0 到顶点 5 的最短路径长度为 3。

✨ 解题步骤详解

以"最短路径"为例，展示如何用 BFS 求无权图的最短路径：

问题： 给定一个无权图和起点 s，求从 s 到每个顶点的最短距离。

解题步骤：

1. 初始化：
   • 创建 dist 数组，所有值初始化为 -1（表示不可达）
   • 设 dist[s] = 0
   • 将 s 入队
2. BFS 循环：
   • 弹出队首节点 v
   • 遍历 v 的所有邻居 u：如果 dist[u] == -1（未访问），设 dist[u] = dist[v] + 1，将 u 入队
3. 输出结果：dist 数组即为所有最短距离

为什么 BFS 能保证最短路径： BFS 是按层展开的，第 k 层的所有节点距离起点恰好是 k。当一个节点第一次被访问时，它一定是通过最短路径到达的，因为更短的路径（更早的层次）已经在之前被处理过了。

✨ 常见错误

1. 在入队之前忘记标记 visited：如果在出队时才标记，同一个节点可能被多次入队，导致效率低下甚至结果错误。正确做法是入队时立即标记。
2. 用 DFS 求最短路径：DFS 找到的路径不一定是最短的。在无权图中，求最短路径必须用 BFS。
3. 忘记处理不连通的情况：如果图不连通，BFS 后某些节点的 dist 仍为 -1，需要根据题意输出"不可达"。
4. 在加权图上使用 BFS：BFS 只适用于无权图（或所有边权重相同的图）。加权图的最短路径需要使用 Dijkstra 或 Bellman-Ford 算法。
5. 队列中存储了过多信息：BFS 的队列只需要存储节点编号，距离信息存在 dist 数组中即可，不需要把整条路径放入队列。

三、课后练习

编程练习

1. 迷宫: L3352