有趣的数据结构算法20——图的深度优先搜索（DFS）算法实现

系统管理员 2024-04-17 05:50 34阅读 0赞

### 有趣的数据结构算法20——图的深度优先搜索（DFS）算法实现 ###

*  DFS的实现方法
 *  利用c语言实现BFS
 *  GITHUB下载连接

完成了广度优先遍历，还需要完成深度优先遍历噢！图的基本概念和广度优先遍历的方法可以看我的另一篇博文。  
[https://blog.csdn.net/weixin\_44791964/article/details/100038213][https_blog.csdn.net_weixin_44791964_article_details_100038213]  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# DFS的实现方法 #

深度优先搜索与树的先序遍历过程类似。首先遍历根结点，再遍历其子节点。  
本文将以下图为例讲述如何实现DFS。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]  
具体遍历的过程如下：  
1、创建一个visited数组，用来记录已被访问过的点；  
2、从图中的a开始访问，将的visited\[0\]数组的值设置为1。  
3、检查a所有的邻接点n，若visited\[n\]的值为0，则代表该点尚未被访问过；访问n，并将visited\[n\]置为1。将邻接点n设置为新的顶点，重复步骤3。直至最新的被访问过的顶点没有未被访问的邻接点为止。  
4、返回前一个被访问过的但仍有未被访问邻接点的顶点，继续访问该顶点的下一个未被访问邻接点。  
5、重复步骤3、4直到所有点被访问。  
假设顶点数组的存储顺序为：a、b、c、d、e、f。  
那么DFS的遍历结果为：  
a b d c f e。  
接下来我将具体展示如何进行DFS：  
**白底代表尚未访问，黄底代表已经访问！**  
1、初始状态。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 1]  
2、访问a点，根据顶点数组的存储顺序，visited\[0\]设为1；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 2]  
3、访问其周围所有邻接点，若对应visited\[n\]的值为0，则代表该顶点尚未被访问过，访问之；并将该临界点设为顶点重新开始访问，访问顺序根据顶点数组的存储顺序决定，存储顺序为a b c d e f，根据存储顺序，此时访问到点b。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 3]  
4、以点b为顶点开始重新搜索邻接点，根据存储顺序，首先搜索到点c，二者不邻接；再次搜索到点d，由于点d尚未被访问且是临界点，访问点d。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 4]  
5、重复上述步骤，直至最新的被访问过的顶点没有未被访问的邻接点为止。此时搜索到顶点d的邻接点c，点c没有未被访问的邻接点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 5]  
6、由于顶点c没有未被访问的邻接点，返回前一个被访问过的但仍有未被访问邻接点的顶点，此时返回顶点d，继续访问该顶点的下一个未被访问邻接点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 6]  
7、将f设为新顶点开始搜索。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 7]  
此时便完成了所有顶点的访问。在接下来的时间里，会依次回退搜索，由于visted数组全为1，访问结束。

# 利用c语言实现BFS #

#include<stdlib.h>
    #include<stdio.h>
    
    #define VexNum 100
    
    typedef struct Graph			//利用邻接矩阵表示
    {
        
    	char vexs[VexNum];			//顶点
    	int arcs[VexNum][VexNum];	//边	
    	int vexnum, arcnum;			//顶点和边的数量
    }Graph;
    
    int LocateVex(Graph *G, char c)	//输入顶点符号，寻找其对应的位置
    {
        
    	for (int i = 0; i < G->vexnum; i++)
    	{
        
    		if (G->vexs[i] == c)
    			return i;
    	}
    }
    
    void initGraph(Graph *G)					//图的初始化
    {
        
    	int i, j;
    	char c1, c2;
    
    	scanf("%d %d", &G->vexnum, &G->arcnum);
    	getchar();
    
    	for (i = 0; i < G->vexnum; i++)
    	for (j = 0; j < G->vexnum; j++)
    		G->arcs[i][j] = 0;				//初始化每条边为0
    
    	for (i = 0; i < G->vexnum; i++)
    		scanf("%c", &G->vexs[i]);			//输入点的信息
    
    	for (int k = 0; k < G->arcnum; k++)			//创建边的信息
    	{
        
    		getchar();
    		scanf("%c%c", &c1, &c2);			//输入一条边依附的顶点
    		i = LocateVex(G, c1);				//找到顶点i的下标
    		j = LocateVex(G, c2);				//找到顶点j的下标
    
    		G->arcs[i][j] = G->arcs[j][i] = 1;
    	}
    }
    
    bool visited[VexNum];
    
    void DFS(Graph *G,char c0)					//从c0开始遍历整个图
    {
         
    	int index0, i;
    	char e;
    
    	index0 = LocateVex(G, c0);
    	visited[index0] = 1;
    	printf("%c ", c0);
    
    	for (i = 0; i < G->vexnum; i++)
    	{
        
    		if (G->arcs[index0][i] && !visited[i])
    		{
        
    			e = G->vexs[i];
    			DFS(G, e);						//以下一个邻接点为顶点开始搜索
    		}
    	}
    }
    
    void main(){
        
    	Graph G;
    	initGraph(&G);
    	for (int i = 0; i < G.vexnum; i++){
        
    		visited[i] = 0;
    	}
    	DFS(&G,'a');
    }

输出结果为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 8]

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[https_blog.csdn.net_weixin_44791964_article_details_100038213]: https://blog.csdn.net/weixin_44791964/article/details/100038213
[20190723170158884.jpg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/ed3e251b59ba4cdf8326027bcc624b83.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/6f3fd72aec8c4941b189c165f4d3703f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/0f27317135ff4f5ea66213b401459d75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/fa5ebfab25c943999d8234bcfc338c6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/570c732c968643539cdd2314febdca5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/c3c3a1632a9e4995a0a3f2ef9007cb35.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/851784959b5d4ff3b3332a32817f978f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/9b238fb67b8041c39aa3bc4d67f89085.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/6c63cf5e8495488dbe404ddc1fb798ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/66580880c0664c849cf0d59c7de343d7.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm