图的DFS(深度优先搜索)C语言详解

﹏ヽ暗。殇╰゛Y 2023-05-28 05:11 47阅读 0赞

**实现如图的DFS（邻接矩阵）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]  
**核心代码**

//********************深度优先的递归算法********************
    void DFS(MGraph G, int i)
    { 
    	int j;
    	visited[i] = 1;
    	printf("%c", G.verx[i]);			//输出顶点信息
    	for (j = 0; j < G.numVertexes; j++)
    		if (G.arc[i][j] < INFINITY && !visited[j])			//有边且没有被访问
    			DFS(G, j);										//对没有被访问的结点，递归调用
    }

**编译环境：vc6.0,代码如下**

/* 顶点数据类型为char,边上权值类型为int */
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXVEX 100 //最大顶点数
    #define INFINITY 99999 //用99999表示无限大
    
    int visited[MAXVEX];				//访问标志数组,其值为1或0，1代表已访问，0代表没访问
    
    //********************邻接矩阵存储结构代码********************
    typedef struct
    { 
    	char verx[MAXVEX];					//顶点表
    	int arc[MAXVEX][MAXVEX];			//边表
    	int numVertexes, numEdges;			//图中当前顶点数和边数
    }MGraph;
    
    //********************建立无向图的邻接矩阵表示********************
    void CreateMGraph(MGraph* G)
    { 
    	int i, j, k, w;
    	printf("输入顶点数和边数\n");
    	scanf("%d%d", &G->numVertexes, &G->numEdges);
    	getchar();										//获取缓冲区的回车符
    	for (i = 0; i < G->numVertexes; i++)			//读入顶点信息
    	{ 
    		printf("输入第%d个顶点信息\n", i + 1);
    		scanf("%c", &G->verx[i]);
    		getchar();										//获取缓冲区的回车符
    	}
    	for (i = 0; i < G->numVertexes; i++)					//矩阵初始化
    		for (j = 0; j < G->numVertexes; j++)
    			if (i == j)										//如果i==j;矩阵的主对角线都为0
    				G->arc[i][j] = 0;
    			else G->arc[i][j] = INFINITY;                    //否则，矩阵初始化，都是无穷大
    	for (k = 0; k < G->numEdges; k++)						//建立邻接矩阵
    	{ 
    		printf("输入边（vi,vj）上的下标i，下标j和权w：\n");
    		scanf("%d%d%d", &i, &j, &w);				//输入边（vi,vj)上的权值w
    		G->arc[i][j] = w;
    		G->arc[j][i] = G->arc[i][j];				//因为无向图矩阵是对称的
    	}
    }
    
    //********************深度优先的递归算法********************
    void DFS(MGraph G, int i)
    { 
    	int j;
    	visited[i] = 1;
    	printf("%c", G.verx[i]);			//输出顶点信息
    	for (j = 0; j < G.numVertexes; j++)
    		if (G.arc[i][j] < INFINITY && !visited[j])			//有边且没有被访问
    			DFS(G, j);										//对没有被访问的结点，递归调用
    }
    
    
    int main()
    { 
    	int i;
    	MGraph G;
    	CreateMGraph(&G);
    
    	printf("深度优先遍历：");
    	for (i = 0; i < G.numVertexes; i++)		//初始化所有顶点都是未访问状态
    		visited[i] = 0;						
    	for (i = 0; i < G.numVertexes; i++)		//对未访问的结点调用DFS,若是连通图，只会执行一次
    		if (!visited[i])
    			DFS(G, i);
    	printf("\n");
    	return 0;
    }

**输出结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/34995994ab5b47d1a15a4eb3732d79a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/9e611252548d48ac9abd44d58f405296.png