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出队列，最终生成的遍历序列如下图所示