图 · 单步演示
广度优先搜索（BFS）
从起点出发，先访问所有距离为 1 的顶点，再访问距离为 2 的，一圈一圈往外扩。靠队列记住待访问的顶点，入队时就打标记，避免重复入队。
队列（头 → 尾）（空）
访问顺序（空）
步 001 / 026从 A 出发做广度优先搜索：离起点近的顶点先访问。邻居按名称顺序处理。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
标记 s；Q ← [s]while Q 非空u ← Q 出队；访问 ufor v in u 的邻居（按名称顺序）if v 未标记：标记 v；v 入队
变量
| u | — |
|---|---|
| 已标记 | [] |
| 队列 | [] |
复杂度
| 最好情况 | O(V + E) |
|---|---|
| 平均情况 | O(V + E) |
| 最坏情况 | O(V + E) |
| 额外空间 | O(V) |
用邻接表存图时，每个顶点入队出队一次，每条边从两端各看一次。用邻接矩阵存图时要扫整行，变成 O(V²)。
要点
- 在不带权的图上，BFS 第一次到达某个顶点时走的边数就是最短的。
- 邻居的处理顺序会影响访问顺序，但不影响每个顶点离起点的层数。
常见错误
出队时才打标记，同一个顶点可能被多次放进队列；在入队时就标记更省事。