广度优先搜索（BFS）
一层一层地探索图。由队列决定下一个顶点，所以总是先访问离起点最近的顶点。
- 时间 O(V + E)
- 内存 O(V)
- 使用队列
这些是什么意思？
- 顶点：图中的一个点，这里画成带字母的圆圈。
- 边：连接两个顶点的线。这里两个方向都能走。
- 邻居：通过一条边与某个顶点相连的顶点。按字母顺序查看。
- 队列：先进先出。BFS 总是取出等得最久的顶点。
- 栈：后进先出。DFS 总是从最后到达的顶点继续往下走。
- V 和 E：顶点数和边数。O(V + E) 表示每个顶点和每条边只被处理固定的次数。
0 / 60 步
- 在队列中
- 当前
- 已完成
- 搜索树的边
- 跳过的边
从 A 开始。点击播放，或一步一步查看搜索过程。
空格键：播放或暂停。左右方向键：单步移动。Home 和 End 键：跳转。
试试看： 选择分成两部分的图。没有和起点连通的顶点永远到达不了。
工作原理
BFS 先把起点放进队列。然后反复取出队列最前面的顶点，把它的新邻居加到队列末尾。队列按到达顺序处理，所以距离一条边的顶点全部完成后，才轮到距离两条边的顶点。顶点旁边的数字是它到起点的距离：到达它最少需要几条边。
适用场合
需要按步数算的最短路径时，用 BFS：谜题的最少步数、网络中的最少跳数、和你相隔不超过两层关系的人。在大图上队列可能很长，因为它一次要装下整整一层。