一起动脑筋 · 先看一个小故事
每走一格都花同样一步，机器人像水波一样向外找出口。第一波碰到出口时意味着什么？
把过程摊开来看
- 起点距离 0
- 相邻格距离 1
- 再相邻距离 2
- 首次出口最少步数
在无权图或每条边代价相同的情况下，BFS 可找到最少边数的路径。
它先探索所有更少步数能到的点，因此不会漏掉更短的路线。要还原路径，还需记录从哪里走来。
观察队列怎样决定探索顺序
图的边是 A—B、A—C、B—D、C—E。邻居按字母顺序入队，左边是队首。
A
已发现 A，距离是 0。
BC
把尚未发现的 B、C 入队并标记，它们距离为 1。
CD
D 入队，距离为 2。C 仍排在 D 前面。
DE
E 入队，距离为 2。第一层已处理完。
空队列
没有未发现的新邻居。本例访问顺序 A、B、C、D、E。
01为什么 BFS 能找最短步数？
BFS 的访问顺序是：
0 步→1 步→2 步→3 步...
因此一个节点第一次被发现时，不可能存在步数更少但还没处理到的路径。
02怎样记录距离？
std::vector<int> dist(n, -1);
std::queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}03dist=-1 为什么有用？
它同时表示“这个节点还没有被访问”。
第一次设置 dist[v] 时，就得到了从起点到 v 的最短边数。
04怎样恢复一条最短路径？
可以额外记录每个节点第一次被发现时的前驱：
parent[v] = u;到达终点后，从终点沿 parent 反向走回起点，再把顺序翻转。
05什么时候普通 BFS 不适用？
如果不同边的代价不同：
每条边都算 1 步
BFS 可以求最少边数。
边有不同权重
普通 BFS 不保证总代价最小。
06带权图该怎么办？
如果边权非负，常见算法是 Dijkstra；如果权重还有其他特殊性质，也可能有别的方法。
你已经知道了什么
- BFS 按步数从小到大探索。
- 无权图中第一次到达节点时的距离就是最短步数。
- dist 可以记录距离，也可以兼任访问状态。
- parent 可以恢复一条最短路径。
- 边权不同的最短路不能直接使用普通 BFS。
下一篇：DFS 和 BFS 有什么区别？
轮到你来试一试
一条路线两段各 10 分钟，另一条三段各 1 分钟，少段数的就最快吗？
想好了吗？点开看解释
不是。两段要 20 分钟，三段只要 3 分钟。这时不能把普通 BFS 的层数直接当用时。