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

逃离我推掉我的手 2024-04-18 16:33 41阅读 0赞

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

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

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

**目录**

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

定义

图的存储结构及方法

伪代码实现

性能分析及应用

性能分析

应用

参考文献

--------------------

## 定义 ##

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

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

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

## 图的存储结构及方法 ##

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

## 伪代码实现 ##

/*****************************
    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.