广度优先搜索 Breadth-First Search

解决最短路径问题的算法被成为广度优先搜索。

步骤

1、 使用图来建立模型
2、 使用广度优先搜索解决问题

图有节点和边构成。
一个节点可能和众多节点直接相连，这些节点被成为邻居。

队列

队列是一种先进先出 (first in first out )的数据结构，而栈是一种后进先出 ( last in first out) 的数据结构。

有无箭头指向

有向图

无向图

BFS算法

小结：

广度优先搜索指出是否有从A到B的路径
如果有，广度优先搜索将找出最短路径
面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先算法解决问题
有向图汇中的边为箭头，箭头的方向指向了关系的方向。
无向图中的边不带箭头，其中的关系是双向的。
队列是先进先出的。
栈是后进先出的。
你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此必须是队列。
对于检查过的人，务必不要再去检查，否则可能会导致无限循环。