广度优先搜索（BFS）
一层一层地探索图。由队列决定下一个顶点，所以总是先访问离起点最近的顶点。
- O(V + E)
- 内存 O(V)
- 队列
V 和 E：顶点数和边数。O(V + E) 表示每个顶点和每条边只被处理固定的次数。
队列：先进先出。BFS 总是取出等得最久的顶点。
本页的其他术语
- 顶点：图中的一个点，这里画成带字母的圆圈。
- 边：连接两个顶点的线。这里两个方向都能走。
- 邻居：通过一条边与某个顶点相连的顶点。按字母顺序查看。
0 / 60 步
试试看： 选择分成两部分的图。没有和起点连通的顶点永远到达不了。
工作原理
BFS 先把起点放进队列。然后反复取出队列最前面的顶点，把它的新邻居加到队列末尾。队列按到达顺序处理，所以距离一条边的顶点全部完成后，才轮到距离两条边的顶点。顶点旁边的数字是它到起点的距离：到达它最少需要几条边。
适用场合
需要按步数算的最短路径时，用 BFS：谜题的最少步数、网络中的最少跳数、和你相隔不超过两层关系的人。在大图上队列可能很长，因为它一次要装下整整一层。