一圈一圈往外扩——波纹先碰到的岸，就是最近的岸
往池塘中央扔一颗石子，波纹一圈一圈往外扩。岸离石子 1 步的，第 1 圈就被波及；离 2 步的，第 2 圈才轮到。广度优先搜索（BFS，Breadth-First Search）就是"波纹算法"：从起点出发，先把离它 1 步的所有点走完，再走 2 步的，再走 3 步的……。谁被波纹第一次碰到，那个圈数就是最短步数——因为波纹是一步一步扩的，不可能跳过更近的岸。
管理"下一圈要访问谁"的工具是队列（queue）：排队买冰淇淋，先来的先服务（FIFO）。上一课 DFS 用"调用栈"走到底，这一课 BFS 用队列一层一层推——两种搜索，两种气质。
dist 数组记录每个点到起点的步数（-1 = 还没到）。无权图中，首次到达 = 最短步数。还是上一课的演练场，这次看波纹：从 1 号站扔石子，节点颜色 = 波纹第几圈碰到它（dist 值）。紫 = 0 圈（起点），蓝 = 1 圈，橙 = 2 圈，绿 = 3 圈；7 号孤岛永远碰不到（dist = -1）。
波纹一圈只扩一步。假设某条路 3 步能到 6 号站，那波纹第 3 圈一定会碰到它——不可能第 3 圈还没到、第 4 圈才到（那说明 3 步的路走不通，矛盾）。所以首次被碰到的圈数，就是最短步数，一个不多一个不少。
对照演练场：6 号站在第 3 圈才被碰到（1→2→4→6 或 1→3→5→6，都是 3 步）。DFS 上一课找到的"1→2→4→6→5"是 4 条边的绕路——BFS 不会犯这个错，因为它先看所有 1 步、再看所有 2 步，近的永远先于远的。
工具两样：队列（排队，先进先出）+ dist 数组（初始全是 -1 = 没到过，起点 dist = 0）。规则：出队一个 u → 看它所有邻居 → 没到过（dist=-1）的，dist 记成 dist[u]+1，进队。手推演练场（起点 1）：
// 每行：出队 u → 新发现的邻居 → 出队后的队列 → 新写的 dist
出队 1 发现 2,3（dist=1） 队列: [2 3] dist: 1:0 2:1 3:1
出队 2 发现 4（dist=2） 队列: [3 4] dist: 4:2
出队 3 发现 5（dist=2） 队列: [4 5] dist: 5:2
出队 4 发现 6（dist=3） 队列: [5 6] dist: 6:3
出队 5 6 已发现（dist=3），跳过 队列: [6]
出队 6 4,5 都已发现，跳过 队列: [] → 结束
（7 号孤岛始终没被发现，dist[7] = -1）
关键性质：队列先进先出，所以 1 步的点（2、3）一定排在 2 步的点（4、5）前面被处理，2 步的又排在 3 步的（6）前面——队列天然按层排好了队，这就是"波纹一圈一圈"的代码实现。
// g 是邻接表；dist 初始全 -1 void bfs(int s) { queue<int> q; q.push(s); dist[s] = 0; // 起点入队、记账 0 步 while (!q.empty()) { int u = q.front(); q.pop(); // 队头出队（先来的先服务） for (int v : g[u]) { if (dist[v] == -1) { // 从没到过 → 首次到达 = 最短 dist[v] = dist[u] + 1; // 入队那一刻记账 q.push(v); } } } }
和 DFS 递归版对照着读：DFS 的"回溯"是函数 return，BFS 的"换圈"是队列 pop。DFS 用调用栈记住来路，BFS 用队列记住"下一圈名单"。dist 只在 dist[v] == -1 时写一次——这就是"首次到达即最短"的代码形式。
DFS BFS
走法 一条路走到底，再回头 一圈一圈扩（按层）
数据结构 调用栈（递归） 队列（先进先出）
回答 能不能到？有哪些点能到？ 最少几步到？
找到的路 不一定是最近的 一定是最短的（无权图）
典型题 连通块计数、迷宫找任一路径 最少步数、最少换乘、跳板问题
一句话 "走透一块" "先近后远"
判断口诀：题目问"最少几步 / 最近 / 最少换乘"→ BFS；问"能不能到 / 有几块 / 任意一条路"→ DFS 也行，BFS 也行。两种搜索都能数连通块（BFS 同样可以外层循环开新轮），但 BFS 的独门绝活是最短路，DFS 的独门绝活是走透（比如后续要学的深度信息、拓扑排序）。
同一张演练场图，BFS 从 1 出发，输出每个站到 1 的最短步数（-1 = 到不了）。
// 图 BFS：最短路（步数） #include <bits/stdc++.h> using namespace std; int n; vector<vector<int>> g; vector<int> dist; void bfs(int s) { queue<int> q; q.push(s); dist[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } } int main() { n = 7; g.assign(n + 1, {}); auto add = [&](int a, int b) { g[a].push_back(b); g[b].push_back(a); }; add(1, 2); add(1, 3); add(2, 4); add(3, 5); add(4, 6); add(5, 6); // 7 号孤岛 dist.assign(n + 1, -1); bfs(1); for (int i = 1; i <= n; i++) printf("1→%d: %d 步\n", i, dist[i]); // 输出： // 1→1: 0 步 1→2: 1 步 1→3: 1 步 // 1→4: 2 步 1→5: 2 步 1→6: 3 步 // 1→7: -1 步（孤岛，到不了） return 0; }
dist[v] = dist[u] + 1 必须在入队时写；写在"出队时"是常见错（同一个点可能被不同人提议，值会乱）。② dist 初始必须全 -1，起点单独置 0。③ 输出 -1 时要翻译成"不可达"，别直接打印 -1 步。if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }——首次记账即最短步数。