图的深度优先遍历算法

男娘i 2021-11-11 13:42 417阅读 0赞

**1. 实验目的**

（1） 掌握图的逻辑结构；

（2） 掌握图的邻接矩阵存储结构；

（3） 验证图的邻接矩阵存储及其深度优先遍历操作的实现。

**2. 实验内容**

（1） 建立无向图的邻接矩阵存储；

（2） 对建立的无向图，进行深度优先遍历；

**3. 实验提示**

定义邻接矩阵存储的无向图结构体MGraph，在其基础上实现题目要求的图建立、深度优先遍历等基本操作。

**4. 程序代码**

#include <iostream>
    using namespace std;
    #define MAX_VERTEX 20  
    typedef char DataType;
    typedef struct
    {
    	int vertexNum;
    	DataType vertexArr[MAX_VERTEX];       //顶点元素数组	 
    	int edgeArr[MAX_VERTEX][MAX_VERTEX]; //边矩阵二维数组 
    	
    }ArrayGraph;
    
    int visited[MAX_VERTEX] = {0};
    void ArrayGraph_init(ArrayGraph *pGraph);
    void ArrayGraph_create(ArrayGraph *pGraph);
    void ArrayGraph_show(ArrayGraph *pGraph);
    void DFTraverse(ArrayGraph *pGraph, int i);
    
    int main()
    {
    	ArrayGraph g;
    	ArrayGraph_init(&g);       //初始化图 
    	ArrayGraph_create(&g);     //创建图 
    	ArrayGraph_show(&g);       //打印图 
    	printf("深度优先遍历序列是：");
    	DFTraverse(&g, 0);
    	system("pause");
    	return 0;
    
    }
    //初始化为一个无圈图 ，也就是边矩阵中，主对角线元素都是0 
    void ArrayGraph_init(ArrayGraph *pGraph)
    {
    	for (int i = 0; i < MAX_VERTEX; i++)
    		pGraph->edgeArr[i][i] = 0;
    }
    //输入一个图 
    void ArrayGraph_create(ArrayGraph *pGraph)
    {
    	printf("请输入图的顶点个数（不超过20）：");
    	cin>>pGraph->vertexNum;
    	for (int i = 0; i < pGraph->vertexNum; ++i)    //填充顶点数组，也就是输入顶点元素 
    	{
    		printf("输入第%d个顶点值\n", i + 1);
    		scanf_s(" %c", &(pGraph->vertexArr[i]));
    	}
    	for (int j = 0; j <pGraph->vertexNum; ++j)   //填充边关系 
    	{
    		for (int i = j + 1; i < pGraph->vertexNum; ++i)
    		{
    			printf("若元素%c和%c有边，则输入1，否则输入0\t", pGraph->vertexArr[j], pGraph->vertexArr[i]);
    			scanf_s("%d", &(pGraph->edgeArr[j][i]));
    			pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i];     //对称 
    		}
    	}
    }
    void ArrayGraph_show(ArrayGraph *pGraph)
    {
    	printf("\n\n顶点元素如下\n");
    	for (int i = 0; i < pGraph->vertexNum; ++i)
    	{
    		printf("%-5c", pGraph->vertexArr[i]);
    	}
    	printf("\n\n");
    	puts("边矩阵如下\n\n");
    	printf("%-2c", ' ');
    	for (int i = 0; i<pGraph->vertexNum; ++i)
    		printf("%-5c", pGraph->vertexArr[i]);
    	putchar('\n');
    	for (int j = 0; j <pGraph->vertexNum; ++j)
    	{
    		printf("%-2c", pGraph->vertexArr[j]);
    		for (int i = 0; i < pGraph->vertexNum; ++i)
    		{
    			printf("%-5d", pGraph->edgeArr[i][j]);
    		}
    		putchar('\n');
    	}
    	printf("\n\n");
    }
    void DFTraverse(ArrayGraph *pGraph, int i) 
    {
    	printf("%-5c", pGraph->vertexArr[i]);
    	visited[i] = 1;
    	for (int j = 0; j < pGraph->vertexNum; j++) {
    		if (pGraph->edgeArr[i][j] == 1 && visited[j] == 0)
    			DFTraverse(pGraph, j);
    	}
    }

**5. 运行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70][]

**6. 实验心得**

图的创建和深度优先遍历比较好掌握，倒是花了不少时间思考图的打印问题。最终成果还是非常令我满意的。通过一次次修改和尝试，我对图的遍历、创建和打印有了更深的体会。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70]: /images/20211109/515f47f2e91a41adacb53c4edbeed0aa.png