目录
前言
深度优先遍历（DFS）
1.基本概念
2.算法思想
3.二叉树的深度优先遍历（例子）
图的深度优先遍历
1.图(graph)邻接矩阵的深度优先遍历
思路分析
代码实现
2.图(graph)邻接表的深度优先遍历
思路分析
代码实现
递归代码
非递归代码
3.邻接矩阵和邻接表对比
在前面学习过二叉树的时候我们就已经接触到深度优先搜索和广度优先搜索，二叉树的前序遍历和后序遍历都属于深度优先遍历的一种，但是对于二叉树这种有规律的数据结很容易理解，但是如果是对于图这种没有规律的数据结构又该如何去实现深度优先和广度优先遍历呢？下面就一起来看看吧！
1.基本概念
深度优先搜索是用来遍历或搜索树和图数据结构的算法，它是可以从任意跟节点开始，选择一条路径走到底，并通过回溯来访问所有节点的算法。简单来说就是通过选择一条道路走到无路可走的时候回退到上一个岔路口，并标记这条路已走过，选择另外一条道路继续走，直到走遍每一条路。（一句话概括：一路走到黑，黑了就回头）
2.算法思想
Dfs思修基于递归思想，通过递归的形式来缩小问题规模，把一件事分割成若干个相同的小事，逐步完成。
深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。
否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。
3.二叉树的深度优先遍历（例子）
为了大家更好的了解深度优先遍历的算法，我下面举一个二叉树深度优先遍历的例子，如下图所示的一个二叉树，对其进行前序遍历（深度优先遍历）
结果为： A B D H I E J C F K G
前序遍历就是从根结点出发，一直向左子节点走，直到左子节点不存在然后返回到上一个节点走这个节点的右子节点，然后一直往右子节点走，同样的也是走不通为止就返回。很显然这种一路走到黑，黑了就回头的方式，就是深度优先遍历的过程。
对于二叉树的深度优先遍历大家都很好理解，但是如果对于图的话，那怎么去进行深度优先遍历呢？
如图所示，拿到这么一个图我们从V1开始对其进行深度优先遍历，那么每一次遇到分叉点走不同的路径遍历到的结果是不一样的，所以对于一个图的深度优先变量结果可以为多种。
深度优先遍历算法步骤
- 访问初始结点v，并标记结点v为已访问。
- 查找结点v的第一个邻接结点w。
- 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
- 若w未被访问，对w进行深度优先遍历递归(即把w当做另一个v，然后进行步骤123)
- 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
在此之前我们学习了图的两种储存方式，分别是邻接矩阵和邻接表，那么这两种存储方式进行深度优先遍历结果会有什么不同呢？我们接着看。
1.图(graph)邻接矩阵的深度优先遍历
思路分析
如上图所示，从2位置开始进行深度优先遍历，由于图可能是具有环形结构的，为了避免进入到环内的死循环，这里我们需要用到一个辅助数组visited来标记某一个顶点是否遍历过，如果遍历过的话，那么就不走这个方向，如果全部的方向都被标记遍历过，那就返回到上一个位置，换一个方向去遍历。（递归算法）
对于visited数组，初始化为0，表示未访问过，如果访问了的话那么就设置为1
最后整个图遍历完成之后，visited数组里面的数组全都为1 ，也就是说这个图已经变量完成了
代码实现
输出结果：
2.图(graph)邻接表的深度优先遍历
思路分析
前面我们学习过了邻接表是由两种节点组成的，分别是头结点和边节点，头结点是用来储存数据的，而变节点是用来储存于当前节点有通路的节点的引索。如图所示
对于邻接表的话，那怎么去书写代码呢？同样的我们还是需要一个visited数组来标记已经访问过的节点，然后对下一个节点进行判断是否访问过，如果没有访问过那么就进入到下一个节点的递归，如果访问过那就换一个方向继续访问，如果都访问过，那就返回到上一个节点的位置重复以上的操作。下面我提供两种代码的书写方式，分别是递归和非递归来去实现深度优先遍历。
代码实现
创建图代码（邻接表）：
递归代码
非递归代码
测试结果：
3.邻接矩阵和邻接表对比
邻接矩阵
对于一个邻接矩阵进行深度优先遍历，要把邻接矩阵上每一个点都进行对比访问，如果这个图有n个顶点的话，所以时间复杂度为O(n^2)
邻接表
用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。
所以可以看出，如果是对于稠密图的话用邻接矩阵更好，而对于稀疏图的话，用邻接表会更好。
以上就是本期的全部内容了，我们下次接着学习图的广度优先遍历，下次见咯！
分享一张壁纸： 
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/13472.html