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

精品文档 上机实验报告 学 院： 计算机与信息技术学院专 业： 计算机科学与技术(师范）课程名称： 数据结构实验题目：深度优先遍历（邻接矩阵）班级序号： 师范1班学 号： 201421012731 学生姓名： 邓雪指导教师： 杨红颖完成时间：2015年12月25号 1、 实验目的：1掌握图的基本概念和邻接矩阵存储结构。2掌握图的邻接矩阵存储结构的算法实现。 3掌握图在邻接矩阵存储结构上遍历算法的实现。二、实验环境： Windows 8.1 Microsoft Visual c+ 6.02、 实验内容及要求：编写图的深度优先遍历邻接矩阵算法。建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。四、概要设计：深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。 以图中无向图G4为例，深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4,V8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为： V1V2V4 V8V5V3V6V7五、代码#include #include #define n 8#define e 9typedef char vextype;typedef float adjtype;int visitedn;/定义结构体typedef struct nodevextype vexsn;adjtype arcsnn;graph;graph *ga;/建立无向网络void CREATGRAPH()int i,j,k;float w;printf(请输入各个顶点:);for(i=1;ivexsi=getchar();getchar();for(i=1;i=n;i+)for(j=1;jarcsij=0;printf(n请输入边及其的权：(从1开始输入)n);for(k=0;karcsij=w;ga-arcsji=w;/深度优先遍历void DFS(int i)int j;printf(node:%cn,ga-vexsi);visitedi=1;for(j=1;jarcsij=1)&(!visitedj)DFS(j);/主函数void main()ga=(graph *)malloc(sizeof(graph);CREATGRAPH();DFS(1);六、运行界面七、实验中遇到的问题及总结已经在广度优先遍历中遇到过的问题这次没有再发生，不过最开始出现了一些小问题，花费了很长的时间。通过这几次实验，我变得更加的耐心认真。在以后的学习中我一定会更加努力。八、