一起动脑筋 · 先看一个小故事
女孩在地上画圈：一步能到的地方先看完，再看两步能到的地方。
把过程摊开来看
- 第 0 层起点
- 第 1 层一步可达
- 第 2 层两步首次可达
- 队列保持先后顺序
广度优先搜索按层扩展。
把起点入队，取出一个点后加入尚未发现的邻居。常在入队时标记，避免同一个点反复排队。
观察队列怎样决定探索顺序
图的边是 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（Breadth-First Search，广度优先搜索）会从起点开始一层一层向外扩散。
起点第 1 层第 2 层第 3 层
02为什么像水波？
往水里丢一颗石子，波纹先到近处，再到更远处。
BFS 也是先处理离起点更近的状态，再处理更远的状态。
03BFS 为什么使用队列？
队列是先进先出。
先发现的节点先处理，正好能保证较近的一层先被展开。
发现新节点→加入队尾→从队头依次处理
04基本代码框架
std::queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}05为什么通常在入队时就标记 visited？
如果等到出队时才标记，同一个节点可能被多个前驱重复加入队列。
06BFS 能做什么？
- 按层遍历树
- 无权图最短步数
- 迷宫最短路
- 连通性搜索
- 多源扩散问题
你已经知道了什么
- BFS 按距离层次逐层扩散。
- BFS 通常使用队列。
- 先发现的节点先被处理。
- 通常在第一次发现节点时就标记 visited。
- BFS 是无权最短路的重要基础。
下一篇：用 BFS 找最短的路
轮到你来试一试
起点的所有一层邻居还没处理完，就一路深入十层，还是 BFS 吗？
想好了吗？点开看解释
不是通常的广度优先顺序。BFS 要先处理较近的层。