图BFS核心：最短路径与万能模板

一、图 BFS 核心思想

广度优先搜索：从起点开始，一层一层向外扩散访问

• 先走当前点所有邻居 → 再走邻居的邻居
• 用队列 queue实现
• 无权图中，BFS 走到终点的路径 =最短路径

对比 DFS：

• DFS：一条路走到黑，适合找所有路径
• BFS：层层扩散，适合求最短路径

二、必备结构

1. 邻接表：vector<int> adj[]
2. 访问标记数组：bool vis[]
3. 队列：存储待访问顶点

三、图 BFS 标准万能模板

#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int N = 105; vector<int> adj[N]; bool vis[N]; void bfs(int start) { queue<int> q; q.push(start); vis[start] = true; while(!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; // 遍历所有邻接点 for(int v : adj[u]) { if(!vis[v]) { vis[v] = true; q.push(v); } } } }

四、无向图建图 + 完整测试

void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } int main() { memset(vis, false, sizeof(vis)); addEdge(1,2); addEdge(1,3); addEdge(2,4); addEdge(3,4); addEdge(5,6); cout << "BFS从顶点1遍历："; bfs(1); return 0; }

五、BFS 求无权图最短路径（刷题高频）

增加距离数组 dist []，初始为 - 1 代表未访问

int dist[N]; void bfs_short(int start) { queue<int> q; memset(dist, -1, sizeof(dist)); dist[start] = 0; q.push(start); while(!q.empty()) { int u = q.front(); q.pop(); for(int v : adj[u]) { if(dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } }

dist [end] 就是起点到终点最短步数

六、多连通图完整遍历（统计连通块）

int main() { memset(vis,false,sizeof(vis)); int cnt = 0; for(int i = 1; i <= 6; i++) { if(!vis[i]) { cnt++; cout << "\n第"<<cnt<<"块："; bfs(i); } } return 0; }

七、DFS vs BFS 刷题选型口诀

1. 求最短路径、最少步数、迷宫最短出口→ 用 BFS
2. 求所有路径、回溯、连通块填充、岛屿问题→ 用 DFS
3. 数据量大怕递归栈溢出 → 优先 BFS
4. 路径回溯、组合问题 → 优先 DFS

八、BFS 刷题经典场景

1. 迷宫最短路径
2. 岛屿问题层序扩散
3. 拓扑排序基础
4. 多源最短路
5. 二叉树层序遍历本质就是图 BFS 特例

九、新手易错点

1. 入队时不提前标记 vis，导致重复入队死循环
2. 混淆 DFS 递归、BFS 队列实现方式
3. 求最短路径还用 DFS，得到的不是最短
4. 多连通图只遍历单个起点

十、今日总结

1. BFS = 队列 + 层层扩散遍历
2. 无权图 BFS 天然得到最短路径
3. DFS 深搜、BFS 广搜，两种模板必须熟练默写
4. 图论两大遍历学会，后续最短路径、拓扑排序直接上手