2、深度优先搜索（Depth-First Search）

2.1 什么是深度优先算法

一句话导读：当你玩迷宫游戏的时候，你进入迷宫那一刻，右手摸着墙手不离开，不停前进，直至走出迷宫，此时你使用的就是深度优先搜索。

2.2 图的深度优先搜索

和树不同，图没有根节点，并且是可以回溯的，比如下图所示，为一个 11 节点的图搜索表示

其中：

节点0 ：包含三个出度，分别指向其三个邻接点，分别为节点1、节点2、节点3，同时节点0也是节点2的邻接点。

节点1：包含三个邻接点，分别为节点2、节点4、节点5

节点2：邻接点为节点0、节点1、节点6。

节点3：邻接点为节点6、节点7。

节点4：邻接点为节点1。

节点5：邻接点为节点1、节点6。

节点6：邻接点为节点3。

节点7：没有任何邻接点，因为节点7的出度并没有指向任何节点。或者说其没有任何出度

节点8：和节点7一样，没有任何邻接点

节点9：邻接点为节点8。

节点10：和节点7一样，没有任何邻接点。

2.3 邻接表

下图为 2.2 中图搜索所示图的邻接表形式。可以看到，节点7、节点8、节点10 是没有任何出度和邻接点的。

2.4 邻接矩阵

下图为 2.2 中图搜索所示图的邻接矩阵表示

其中，纵坐标表示 出度节点，横坐标表示 邻接点

比如，下图中：

• 节点0：邻接点为节点1、节点2、节点3
• 节点3：邻接点为节点6、节点7

2.5 图的深度优先搜索遍历过程

2.5.1 栈

图的深度优先遍历是靠栈来完成的，我们首先创建一个空栈

2.5.2 Visited数组

我们借助 Visited数组，来标识当前节点 n 是否被访问过，空值代表 false.

2.5.3 遍历序列

准备一个空的遍历序列，用来存放最终生成的访问元素。

2.5.4 遍历过程

首先，图是没有根节点的，我们可以以任何节点作为其起始节点，下面我就以节点0为起始节点为例，演示一下图的深度搜索过程。

第1步

节点0入栈

第2步

节点0的第一个邻接点入栈

第3步

节点1的第一个邻接点节点2入栈

第4步

节点2的第一个邻接点节点0入栈，但是节点0 visited = true，即已经被访问过，因此顺延节点1,同样节点1也被访问过，因此继续顺延值节点6,节点6入栈并标记访问

第5步

节点6的第一个邻接点也是唯一一个邻接点：节点3入栈

第6步

节点3的第一个邻接点也是唯一一个邻接点：节点7入栈

第7步

节点7没有任何出度和邻接点，此时节点7出栈，回溯至节点3

第8步

节点3的唯一一个邻接点：节点7已经被访问，此时节点3的所有邻接节点均已访问，此时，节点3出栈，回溯至节点6

第9步

同理，此时节点6的唯一一个邻接点：节点3已经被访问，此时节点6的所有邻接节点均已访问，此时，节点6出栈，回溯至节点2

第10步

此时节点2的三个邻接点：节点0、节点1、节点6均已被访问过，因此节点2出栈，回溯至节点1

第11步

此时节点1的三个邻接点：节点2、节点4、节点5其中节点2已被访问，因此节点4入栈

第12步

以此类推，节点4出栈 => 节点5入栈，并回溯至节点1，节点1所有邻接点均已访问。节点1出栈，回溯至节点0

第13步

此时，节点0的所有出度邻接点均已访问，节点0出栈，此时为空栈

第14步
此时，节点8入栈，节点8所有邻接点均已访问，节点8出栈，而后，节点9入栈，而后马上出栈。以此类推，最后，节点10入栈，而后而后马上出栈，生成最终序列，如下图所示

2.6 树的深度优先搜索

由上所述遍历过程，树的深度优先遍历序列如下图所示