好久没有写简书了，上一篇文章小编分享了何为贪心算法。但是在学习图论里一些经典的贪心算法时，我们需要先学习关于图的两个经典的搜索算法：“深度优先搜索”和“广度优先搜索”。今天小编先分享下“深度优先搜索”的知识点。
一、深度优先搜索介绍
深度优先遍历(Depth First Search)，也有称深度优先搜索，简称为 DFS，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程【可以用堆栈来实现深度优先搜索】
二、深度优先搜索图解
1、无向图
G1
该无向图额邻接矩阵如下：
G1的邻接矩阵表示
该无向图邻接表如下：
G1的邻接表表示
对上面的图G1进行深度优先遍历：
（1）【递归实现方法】从顶点A开始：
第1步：访问A。
第2步：访问B(A的邻接点)。 在第1步访问A之后，接下来应该访问的是A的邻接点，即"B,D,F"中的一个。但在本文的实现中，顶点ABCDEFGH是按照顺序存储，B在"D和F"的前面，因此，先访问B。
第3步：访问G(B的邻接点)。 和B相连只有"G"(A已经访问过了)
第4步：访问E(G的邻接点)。 在第3步访问了B的邻接点G之后，接下来应该访问G的邻接点，即"E和H"中一个(B已经被访问过，就不算在内)。而由于E在H之前，先访问E。
第5步：访问C(E的邻接点)。 和E相连只有"C"(G已经访问过了)。
第6步：访问D(C的邻接点)。
第7步：访问H。因为D没有未被访问的邻接点；因此，一直回溯到访问G的另一个邻接点H。
第8步：访问(H的邻接点)F。
因此访问顺序是：A -> B -> G -> E -> C -> D -> H -> F。
（2）【堆栈实现方法】从顶点A开始：
第1步：建立堆栈stack。
第2步：把顶点A标记为已访问，并压入栈stack。【A】
第3步：栈里第一个元素A的第一个邻接点为B，且B未被访问过，标记为已经访问，然后压入栈stack。【A、B】
第4步：B的邻接点为”A和G”，A已经访问过，所以访问G，将G标记为已访问然后压入栈stack。【A、B、G】
第5步：G的邻接点为”B、E和H”。B已经访问过，且E在H之前，所以先访问E。将E标记为已访问，然后压入堆栈stack。【A、B、G、E】
第6步：E的邻接点为”C和G”。G已经访问过，所以访问C。将C标记为已访问，然后压入栈stack。【A、B、G、E、C】
第7步：C的邻接点为”D和E”。E已经访问过，所以访问D。将D标记为已访问，然后压入栈stack。【A、B、G、E、C、D】
第8步：D的邻接点为”A和C”。都已经访问过，所以从堆栈中弹出D。【A、B、G、E、C】
第9步：此时栈顶元素为C，C的邻接点为”D和E”，都已经访问过，所以接着从堆栈中弹出C。【A、B、G、E】
第10步：此时栈顶元素为E，E的邻接点为”C和G”，都已经访问过，所以接着从堆栈中弹出E。【A、B、G】
第11步：此时栈顶元素为G，G的邻接点为”B、E和H”，”B、E”都已经访问过，H未访问，所以接下来访问H，将H标记为已访问，然后压入栈stack。【A、B、G、H】
第12步：此时栈顶元素为H，H的邻接点为”F和G”，G已经访问过，F未访问，所以接下来访问F，将F标记为已访问，然后压入栈stack。【A、B、G、H、F】
第13步：此时栈顶元素为F，F的邻接点为”A和H”，都已经访问过，所以接着从堆栈中弹出F。【A、B、G、H】
第14步：此时栈顶元素为H，H的邻接点为”F和G”，都已经访问过，所以接着从堆栈中弹出H。【A、B、G】
第15步：此时栈顶元素为G，G的邻接点为”B、E和H”，都已经访问过，所以接着从堆栈中弹出G。【A、B】
第16步：此时栈顶元素为B，B的邻接点为”A和G”，都已经访问过，所以接着从堆栈中弹出B。【A、B】
第17步：此时栈顶元素为A，A的邻接点都已经访问过，所以接着从堆栈中弹出A，此时堆栈为空。【】
因此访问顺序是：A -> B -> G -> E -> C -> D -> H -> F【也就是标记的顺序就是访问的顺序】
对照邻接表以及邻接矩阵，可以得到更好的理解。
2、有向图
G2
该有向图的邻接矩阵如下所示：
G2的邻接矩阵表示
该有向图邻接表如下：
G2的邻接表表示
对上面的图G2进行深度优先遍历
（1）【递归实现方法】从顶点A开始：
第1步：访问A。
第2步：访问(A的出度对应的字母)B。 在第1步访问A之后，接下来应该访问的是A的出度对应字母，即"B,D,F"中的一个。但在本文的实现中，顶点ABCDEFGH是按照顺序存储，B在"D和F"的前面，因此，先访问B。
第3步：访问G(B的出度对应的字母)。 B的出度对应字母只有G。
第4步：访问E(G的出度对应的字母)。 G的出度对应字母只有E。
第5步：E无出度，回溯到A。
第6步：访问(A的出度对应字母)D。因为顶点B已经访问了，由于D在F前面，所以先访问D。
第7步：访问C(D的出度对应的字母)。
第8步：C的出度对应字母为E。已经访问过，所以一直回溯到A。
第9步：访问A剩下的另一个邻接点F。
第10步：访问H(F的出度对应的字母)。
第11步：H的出度对应的字母为G，已经访问过，一直回溯到A，发现已经没有邻接点，遍历结束。
因此访问顺序是：A -> B -> G -> E -> D -> C -> F -> H。
（2）【堆栈实现方法】从顶点A开始-------》这部分同上分析即可这里省略
三、代码实现
这部分的代码是在之前小编写的邻接表的基础上添加类方法实现图的深度优先遍历，邻接矩阵这里没有贴代码，大家可以自行分析。
邻接表实现
有误请指正！
网友评论