第四课《交通王国——图上的 BFS》
🌟一、故事开始：交通王国的大麻烦
1、在🚇「交通王国」里，
有很多很多城市。
2、城市之间：
有公路连接。
例如：
1号城 —— 2号城 | | 3号城 —— 4号城3、一天，小骑士阿勇接到任务：
🏰“请用最少的换乘次数到达终点城市！”
4、阿勇突然发现：
❓“咦？这已经不是迷宫了呀！”
5、没错！
今天：
我们正式进入：
🌟图上的 BFS！
🌟二、什么是“图”？
1、很多同学一听：
“图论”
就害怕。
其实：
图一点都不可怕！
2、🌟图是什么？
简单来说：
点 + 连接
就叫：
图（Graph）
3、例如：
（1）🚇地铁站
是点。
（2）🛣️道路
是连接。
（3）于是：
就形成了一张图。
🌟三、图和迷宫有什么区别？
1、🏰迷宫
位置固定：
上下左右2、🚇图
连接不固定。
（1）例如：
1 可以到 3 1 也可以到 7（2）所以：
图更加自由！
🌟四、图的表示方法
1、今天我们图的表示使用：
🌟邻接表！
2、🌟怎么表示：
（1）例如：
1号城市 连接： 2、3、5（2）那么：
g[1] = {2,3,5}（3）意思是：
从1号城市，
可以到：
2
3
5
🌟五、为什么图也能用 BFS？
1、因为：
BFS 本质不是迷宫！
2、而是：
🌊“扩散搜索”
3、在图里：
也是：
从一个点，
一圈圈扩散。
4、例如：
从1号城市出发。
第1层
一步能到：
2 3第2层
两步能到：
4 5 6第3层
三步能到：
7 8像不像：
🌊水波扩散？
🌟六、图上的 BFS 为什么能求最短路？
1、因为：
BFS 按层搜索！
第1层
1条边到达
第2层
2条边到达
第3层
3条边到达
所以：
第一次到达终点，
一定边数最少！
2、这叫：
🌟无权图最短路
🌟七、什么叫“无权图”？
1、简单理解：
每条路长度都一样！
2、例如：
每坐一站地铁，
算1次。
这时候：
BFS 很厉害！
🌟八、第一道图 BFS 题
🎮题目
有5座城市：
1 - 2 | | 3 - 4 - 5问：
从1到5最少经过几条边？
🌟九、如何存图？
1、🌟邻接表代码
vector<int> g[100];2、🌟加边
g[1].push_back(2); g[2].push_back(1);3、表示：
1 和 2 连通。
4、🌟为什么加两次？
因为：
道路可以：
双向通行！
🌟十、图 BFS 的完整思路
🌊步骤
第一步
起点入队。
第二步
取出队头。
第三步
遍历所有邻居。
第四步
没访问过就入队。
🌟十一、参考程序
#include <iostream> #include <queue> #include <vector> using namespace std; vector<int> g[100]; bool vis[100]; struct Node { int id; int step; }; int main() { // 建图 g[1].push_back(2); g[2].push_back(1); g[1].push_back(3); g[3].push_back(1); g[2].push_back(4); g[4].push_back(2); g[3].push_back(4); g[4].push_back(3); g[4].push_back(5); g[5].push_back(4); queue<Node> q; // 起点 q.push({1,0}); vis[1] = true; while(!q.empty()) { Node cur = q.front(); q.pop(); int u = cur.id; // 到达终点 if(u == 5) { cout << "最少经过 " << cur.step << " 条路" << endl; break; } // 遍历邻居 for(int v : g[u]) { if(!vis[v]) { vis[v] = true; q.push({v, cur.step + 1}); } } } return 0; }🌟十二、程序执行过程
1、开始：
队列： 12、扩展：
2 33、继续扩展：
44、继续：
55、第一次到达5：
就是最短！
🌟十三、图 BFS 的核心模板
🌊图 BFS 四步法
第一步
起点入队。
第二步
取出队头。
第三步
遍历邻居：
for(int v : g[u])第四步
合法就入队。
🌟十四、visited 为什么依然重要？
1、假设：
1 ↔ 22、如果没有 visited：
会变成：
1 → 2 → 1 → 2 → 1无限循环！
3、所以：
图 BFS 和迷宫 BFS 一样，
visited 必不可少！
🌟十五、图 BFS 和迷宫 BFS 的区别
| 迷宫 BFS | 图 BFS |
|---|---|
| 上下左右移动 | 按边连接移动 |
| 方向固定 | 邻居不固定 |
| 用方向数组 | 用邻接表 |
🌟但本质完全一样！
🌊都是：
一层一层扩散！
🌟十六、什么时候想到图 BFS？
以后看到：
1、🚇最少换乘
2、🛣️最短路径
3、👥社交关系传播
4、🌐网络连接
🌟就可以想到：
BFS！
🌟十七、课堂挑战题 ⚔️
🎮挑战1
有图：
1 - 2 - 3 | | 4 ----- 5求：
1 到 5 最少几步？
🎮挑战2
如果：
有的边：
更长怎么办？
提示：
目前学的BFS 不适合！
以后要学：
🌟Dijkstra！
🎮挑战3
如果：
地图是单向道路：
1 → 2怎么办？
提示：
只加一条边！
🌟十八、本课最终总结
1、🌊图 BFS 本质：
在图中进行层层扩散！
2、📦核心工具：
queue 队列
3、🛣️BFS 最擅长：
无权图最短路！
4、🌟图的核心：
点 + 边
5、📚存图方式：
邻接表
6、🛑visited 必不可少：
防止重复搜索！
🌟今天真正学会的：
是：
“抽象关系中的 BFS 思维”。
