ARTICLE · 1367749
BFS 广搜:一个模板,吃透三类经典问题
BFS 广搜:一个模板,吃透三类经典问题
—— 层次遍历 · 无权图最短路 · 最小步数 ——
BFS(广度优先搜索,Breadth-First Search)。它是图论里出镜率最高的模板之一,一个最朴素的 BFS,其实同时覆盖了三大类问题:层次遍历、无权图最短路径、最小步数问题。
一、核心模板
先上代码,全文背诵的那种:
void bfs(int s) {queue<int> q;q.push(s);dis[s] = 0; // 起点距离设为 0while (!q.empty()) {int u = q.front(); q.pop();for (int v : adj[u]) { // 遍历 u 的所有邻居if (dis[v] == -1) { // v 还没访问过dis[v] = dis[u] + 1;q.push(v);}}}} |
三个约定先说明:
1. adj[u]:u 的邻接表(图的存储);
2. dis[]:距离/访问标记数组,初始全部为 -1(表示未访问);
3. 入队时立刻标记 dis[v](而不是出队时才标记),这是 BFS 不重复入队的关键,一定记住。
二、模板在干什么?
BFS 的本质是「逐层扩散」:从起点 s 出发,先访问距离为 1 的所有点,再访问距离为 2 的所有点……队列 queue 保证了「先发现的点先扩展」,所以每个点第一次被访问到时,走的步数一定是最少的。
也就是这一句:dis[v] = dis[u] + 1,是整段代码的灵魂——它一边遍历,一边把「最短距离」顺手算了出来。
三、一个模板,三类问题
① 层次遍历
适用题型:树的层序遍历、按层输出、求树的高度、N 叉树的层平均值等。
用法:把 dis[v] == -1 理解为「没访问过」即可,dis 数组只当 visited 用;如果需要按层输出,在 while 里加一层 for (int i = 0, sz = q.size(); i < sz; i++) 固定本层规模。
典型题:LeetCode 102. 二叉树的层序遍历、111. 二叉树的最小深度。
② 无权图最短路径
适用题型:无权(或每条边权值都为 1)图中,求起点到各点、或起点到终点 t 的最短距离。
用法:直接跑模板,答案就是 dis[t]。BFS 第一次到达 t 时经过的边数,就是最短路径长度。
典型题:LeetCode 1091. 二进制矩阵中的最短路径、01 矩阵(多源 BFS:把多个起点一起入队即可)。
③ 最小步数问题
适用题型:迷宫、倒水、交换位置、单词接龙这类「每次操作代价相同、求最少操作次数」的题。
用法:把「每种状态」看成图中的一个点,把「一次合法操作」看成一条边——隐式图建出来了,套上同一个 BFS 模板,dis[t] 就是最少步数。
典型题:LeetCode 127. 单词接龙、433. 最小基因变化、滑动谜题(773)。
四、复杂度
时间复杂度:O(V + E),每个点入队一次、每条边检查一次。
空间复杂度:O(V),队列和 dis 数组的开销。
五、考场口诀















































































