深度优先遍历(邻接矩阵)

《深度优先遍历(邻接矩阵)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上机实验报告学院：计算机与信息技术学院专业：计算机科学与技术(师范）课程名称：数据结构实验题目：深度优先遍历（邻接矩阵）班级序号：师范1班学号：201421012731学生姓名：邓雪指导教师：杨红颖完成时间：2015年12月25号一、实验目的：1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。二、实验环境：Windows8.1MicrosoftVisualc++6.0二、实验内容及要求：编写图的深度优先遍历邻接矩阵算法。建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而

2、后输出图的邻接矩阵。四、概要设计：深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。 以图中无向图G4为例，深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4,V8,V5出发

3、进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为： V1 V2 V4V8 V5 V3 V6 V7五、代码#include#include#definen8#definee9typedefcharvextype;typedeffloatadjtype;intvisited[n];//定义结构体typedefstructnode{vextypevexs[n];adjty

4、pearcs[n][n];}graph;graph*ga;//建立无向网络voidCREATGRAPH(){inti,j,k;floatw;printf("请输入各个顶点:");for(i=1;i<=n;i++)ga->vexs[i]=getchar();getchar();for(i=1;i<=n;i++)for(j=1;j<=n;j++)ga->arcs[i][j]=0;printf("请输入边及其的权：(从1开始输入)");for(k=0;karcs[i][j]=w;ga->arcs

5、[j][i]=w;}}//深度优先遍历voidDFS(inti){intj;printf("node:%c",ga->vexs[i]);visited[i]=1;for(j=1;j<=n;j++)if((ga->arcs[i][j]==1)&&(!visited[j]))DFS(j);}//主函数voidmain(){ga=(graph*)malloc(sizeof(graph));CREATGRAPH();DFS(1);}六、运行界面七、实验中遇到的问题及总结已经在广度优先遍历中遇到过的问题这次没有再发生，不过最开始出现了一些小问题，花费了很长的时间。通过这几次实

6、验，我变得更加的耐心认真。在以后的学习中我一定会更加努力。八、参考文献《数据结构——用C语言描述》