2、广度优先搜索（Depth-First Search）
2.1 图的广度优先搜索
和树不同，图没有根节点，并且是可以回溯的，比如下图所示，为一个 8 节点的图搜索表示
其中：
节点0 ：包含三个出度，分别指向其三个邻接点，分别为节点1、节点2、节点3，同时节点0也是节点2的邻接点。
节点1：包含三个邻接点，分别为节点2、节点4、节点5
节点2：邻接点为节点0、节点1、节点6。
节点3：邻接点为节点6、节点7。
节点4：邻接点为节点1。
节点5：邻接点为节点1、节点2、节点4、节点6。
节点6：邻接点为节点3。
节点7：邻接点为节点6
2.2 邻接表
下图为 2.1 中图搜索所示图的邻接表形式。可以看到，节点7、节点8、节点10 是没有任何出度和邻接点的。
2.3 邻接矩阵
下图为 2.1 中图搜索所示图的邻接矩阵表示
其中，纵坐标表示 出度节点，横坐标表示 邻接点
比如，下图中：
- 节点0：邻接点为
节点1、节点2、节点3 - 节点3：邻接点为
节点0、节点6
2.4 图的广度优先搜索遍历过程
2.4.1 队列
图的广度优先遍历是靠队列来完成的，我们首先创建一个空队列
2.4.2 Visited数组
我们借助 Visited数组，来标识当前节点 n 是否被访问过，空值代表 false.
2.4.3 遍历序列
准备一个空的遍历序列，用来存放最终生成的访问元素。
2.4.4 遍历过程
首先，图是没有根节点的，我们可以以任何节点作为其起始节点，下面我就以节点0为起始节点为例，演示一下图的广度优先搜索过程。
第1步
第2步
节点0出队列，并且节点0的所有邻接点入队列
第3步
节点1出队列，节点1的邻接点入队列，但是此时，节点1的邻接节点节点2已经被访问过了，因此节点5、节点4进队列
第4步
节点2出队列，节点2有两个邻接节点，其中节点0已经被访问，因此，节点6如队列
第5步
节点3出队列，节点3有两个邻接节点，其中节点6已经被访问，因此，节点7入队列
第6步
节点5出队列，节点5有四个邻接节点均已被访问，此时无节点入队列。同理，节点6、节点7出队列，最终生成的遍历序列如下图所示
