第四课《交通王国——图上的 BFS》一、故事开始交通王国的大麻烦1、在「交通王国」里有很多很多城市。2、城市之间有公路连接。例如1号城 —— 2号城 | | 3号城 —— 4号城3、一天小骑士阿勇接到任务“请用最少的换乘次数到达终点城市”4、阿勇突然发现❓“咦这已经不是迷宫了呀”5、没错今天我们正式进入图上的 BFS二、什么是“图”1、很多同学一听“图论”就害怕。其实图一点都不可怕2、图是什么简单来说点 连接就叫图Graph3、例如1地铁站是点。2️道路是连接。3于是就形成了一张图。三、图和迷宫有什么区别1、迷宫位置固定上下左右2、图连接不固定。1例如1 可以到 3 1 也可以到 72所以图更加自由四、图的表示方法1、今天我们图的表示使用邻接表2、怎么表示1例如1号城市 连接 2、3、52那么g[1] {2,3,5}3意思是从1号城市可以到235五、为什么图也能用 BFS1、因为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、邻接表代码vectorint 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; vectorint 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); queueNode 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 思维”。
GESP6级C++考试语法知识（二十九、广度优先搜索（四、 图上 BFS））
发布时间：2026/5/25 13:02:24
第四课《交通王国——图上的 BFS》一、故事开始交通王国的大麻烦1、在「交通王国」里有很多很多城市。2、城市之间有公路连接。例如1号城 —— 2号城 | | 3号城 —— 4号城3、一天小骑士阿勇接到任务“请用最少的换乘次数到达终点城市”4、阿勇突然发现❓“咦这已经不是迷宫了呀”5、没错今天我们正式进入图上的 BFS二、什么是“图”1、很多同学一听“图论”就害怕。其实图一点都不可怕2、图是什么简单来说点 连接就叫图Graph3、例如1地铁站是点。2️道路是连接。3于是就形成了一张图。三、图和迷宫有什么区别1、迷宫位置固定上下左右2、图连接不固定。1例如1 可以到 3 1 也可以到 72所以图更加自由四、图的表示方法1、今天我们图的表示使用邻接表2、怎么表示1例如1号城市 连接 2、3、52那么g[1] {2,3,5}3意思是从1号城市可以到235五、为什么图也能用 BFS1、因为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、邻接表代码vectorint 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; vectorint 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); queueNode 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 思维”。
