图的DFS算法

朴灿烈づ我的快乐病毒、 2023-06-14 10:49 11阅读 0赞

# DFS:depth-first-search #

## 简介 ##

DFS：深度优先遍历

树与图的遍历方式：

*  深度优先遍历
 *  广度优先遍历

其中对于树来说，他的深度优先遍历又可分为：

*  前序
 *  后序
 *  中序

### 思想 ###

1.  访问图中的某一起始顶点v
2.  由v出发，访问与v相连，并且没有被访问过的顶点w
3.  访问与w相邻但是并没有被访问过的顶点x
4.  重复2,3
5.  当不能向下访问的时候，依次退回到最近被访问的顶点
6.  访问直至所有顶点均被访问过

### 示例 ###

**二叉树**  
![二叉树遍历][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70]  
遍历顺序：A-B-D-E-C-F-G

**多叉树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70 1]  
遍历顺序：A-B-E-F-G-C-D-H-I

**图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70 2]  
遍历顺序：A-B-C-D-E-F

**算法**

bool visited[MAX_VERTEX_NUM];	//访问标记数组
    void DFSTraverse(Graph G){
    	for(int v = 0;v < G.vexnum;v++)    //vexnum表示顶点数
    		visited[v] = false;
    	for(int v = 0;v < G.vexnum;v++)
    		if(!visited[v])
    			DFS(G,v);
    }
    
    void DFS(Graph G,int v){
    	//递归思想
    	visite(v);
    	visited[v] = true;
    	for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w)){
    		if(!visited[v])
    			DFS(G,w);
    	}
    }

其中visited用来标记图中的每个节点是否已经被访问了，如果已经访问了，那么将其置为true,否则置为false。其默认值为false。  
为了防止图并非联通图，所以依次循环图中每个节点，看是否被访问，如果没有访问，则从该节点开始进行遍历。  
在DFS中，主要使用了递归，依次遍历与当前节点相连的节点，进行深度搜索。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200626150419287.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200626151435241.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200626152215845.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz,size_16,color_FFFFFF,t_70