1、广度优先搜索（BFS）

1.1 算法的目标

系统地展开搜索图上的所有节点，并根据要求找寻结果。

1.2 算法的思想步骤

类似层级遍历，利用队列实现图的广度优先搜索。

step1：创建一个队列，用于存储当前已经生成的节点。
step2：如上图所示，首先遍历第一层，找到出发顶点A，将其加入队列。
step3：将队列中的元素根据先进先出的规则出队列，找到与出队列相邻的节点，依次将其加入到队列中。
step4：循环step3，直至找到目标结果，返回输出。

1.3 BFS算法的具体实例

目标target；找到节点8的位置

step1：首先创建一个队列queue，存储当前生成的节点1；
step2：开始第一轮循环，当前队列中就只有一个元素1，对其进行弹出队列操作，同时将与弹出的元素相邻的2、3节点压入队列。

step3：开始第二轮循环，当前队列中有两个元素2、3，依次对其进行弹出队列操作，同时将与弹出的元素相邻的4、5，6、7元素压入队列。
step4：开始第三轮循环，当前队列中有四个元素，分别为4、5；6、7，依次按照顺序对其进行弹出队列操作，同时将与弹出的元素相邻的8、9元素压入队列，此时找到目标元素8，即结束搜索，输出相应的结果。

1.4 BFS注意点

BFS 算法扩展的前提是，每个节点可以以任意顺序扩展，也即一个节点与所有它可以扩展的节点距离都相同。