《数据结构与算法》——图的遍历之深度优先搜索（DFS）总结

废话：复习完了广度优先搜索顺带把深搜也复习了吧，要不BFS一个人怪孤单的。BFS的兄弟DFS向我们走来了，他迈着高挑的步伐向我们走来了！

其实一说深搜和宽搜在我头脑中就不由自主地浮现一个场景，在苍茫的大地上，一个矮胖子（BFS）和一个高瘦子（DFS）在那里站着。

目录

《数据结构与算法》——图的遍历之深度优先搜索（DFS）总结

定义

图的存储结构及方法

伪代码实现

性能分析及应用

性能分析

应用

参考文献

---

定义

什么是深度优先搜索？这个我们可以根据中国传统文化中一些内容就明白了，一个家族中假如说小辈儿里边只有三个人长子、次子、长孙，他们的地位排名是如何的呢？长子>长孙>次子，好，例子就举到这里，再往下说就不对了????。DFS是优先搜索第一个邻接点的子结点，直至无子结点或者全部遍历完，就是尽可能 “深”地搜索一张图。

其基本思想是：从图的一个顶点W出发，首先先访问其未被访问的邻接结点v1，然后从v1出发访问v1未被访问的邻接结点v2，直至不能再向下访问，然后回退一位，重复以上步骤，直至所有的顶点均被访问。

这个算法利用到了一个最基本的思想叫做递归，当然代替递归我们也可以使用栈来代替。

图的存储结构及方法

关于图的存储结构这一块已经在上一篇博客中进行了总结，这里便不再进行赘述。

伪代码实现

/*****************************
Description: 图的深度优先搜索
******************************/
#define MAX_VERTEX_NUM 100 
bool visited[MAX_VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G){
	//对图进行深度优先遍历，设访问函数为visit()
	for(int i = 0;i<G.vexnum;i++)//对标记数组进行初始化 
		visited[i]=0; 
	InitQueu(Q);//辅助队列Q初始化
	for(int i = 0;i<G.vexnum;i++)
		if(!visited[i])
			DFS(G,i);
}

void DFS(Graph G,int v){
	visit(v);
	visited[v]=1;
	for(w=FirstNeighbor(G,v);w!=-1;w=NextNeighbor(G,v,w))
		if(!visited[w])//当前结点未访问过 
			DFS(G,w);		
}//DFS

说明：在BFS和DFS的算法中均使用的是双重循环，目的是避免当前图是非联通的。若图是连通图，则在Traverse中的循环就不会有任何作用。

性能分析及应用

性能分析

空间复杂度：

无论是否使用递归来实现此方法，均需要借助一个工作栈，n个结点均需要入栈一次，所以空间复杂度为o(|V|)。

时间复杂度：

对于邻接矩阵法，需要将整个矩阵遍历一次，所以时间复杂度为o(|V|^2);

对于邻接表来讲，需要将每个顶点和顶点下的边表结点访问一次，所以时间复杂度为o(|V|+|E|)。

应用

1.可以用来生成深度优先生成树（连通图产生）或深度优先生成森林（非连通图产生），若存储方式是邻接矩阵则生成树唯一，若存储方式是邻接表则生成树不唯一。

参考文献

严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京： 清华大学出版社，2013.

王道论坛 2019年数据结构考研复习指导[M]. 北京： 电子工业出版社，2018.

 

 

如有错误，还请朋友不吝指正。