《数据结构图遍历.doc》由会员分享，可在线阅读，更多相关《数据结构图遍历.doc（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构图的遍历实验报告一学号:姓名:完成日期:题目图的遍历一.问题描述从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。试编写一个程序，完成对图的遍历。二.算法设计2.1设计思想1以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。2分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图
2、的算法的基础。2.1.1图的遍历介绍2.1.2基本概念图的遍历:图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。图的1/20遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。2.1.3分类按照搜索途径的不同，图的遍历可分为：深度优先遍历（Depth-FirstTraverse）和广度优先遍历（Breadth-FirstTraverse）两大类。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。（ 1）深度优先
3、遍历(Depth-FirstTraverse)特点：尽可能先对纵深方向的顶点进行访问xx优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能
4、先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。.xx优先搜索的过程a基本思想:2/20首先访问图中某一个指定的出发点Vi；然后任选一个与顶点Vi相邻的未被访问过的顶点Vj；以Vj为新的出发点继续进行深度优先搜索，直至图中所有顶点均被访问过。b具体过程:设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y
5、出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。(2)广度优先遍历（Breadth-FirstTraverse）:特点：尽可能先从指定的出发点，横向地访问图中各个顶点。xx优先遍历的定义在访问了起始点之后,首先依次访问起始点的各个邻接点,然后依次访问那些顶点中未被访问过的邻接点
6、.依此类推,直到所有被访问到的顶点的邻接点都被访问过为止.广度优先搜索的过程a 算法基本思想：首先访问图中某一指定的出发点Vi；然后依次访问Vi的所有接点Vi1，Vi2Vit；3/20再次访问Vi1，Vi2，Vit的邻接点中未经访问过的顶点，依此类推，直到图中所有顶点均被访问为止。b 具体过程：从广度优先搜索遍历方法可知，先被访问的顶点的邻接点也被访问，即假设顶点V在W之前被访问，那么顶点V的所有未经访问的邻接点也在顶点W的所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一个队列结构，用以保存已访问过的顶点的序号，访问该顶点的所有未经访问的顶点。广度优先搜索是一种分层的搜索过
7、程，每向前走一步可能访问一批顶点，不像深度优先搜索那样会出现回退的现象。因此它不是个递归的过程。为了实现逐层访问，算法中使用了一个队列以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为了避免重复访问，需要一个辅助函数visitvex给被访问过的顶点加标记。2.2概要设计规格说明：数据类型及函数定义定义图typedefstructintVM;intRMM;intvexnum;Graph;创建图voidcreatgraph(Graph*g,intn)4/20打印图的邻接矩阵voidprintgraph(Graph*g)访问顶点voidvisitvex(Graph*g,intvex)xx
8、递归遍历voiddfs(Graph*g,intvex)队列的基本操作定义队列typedefstructintVM;intfront;intrear;Que;判断队列是否为空quempty(Que*q)入队操作enque(Que*q,inte)出队操作deque(Que*q)xx 遍历voidBESTraverse(Graph*g)5/20本程序包含四个模块：主程序模块voidmain()构造一个图；打印图的邻接矩阵进行xx优先遍历图；进行xx优先遍历图；2.3功能注释本程序划分为三个不同的模块分别编译。其优点在于编译时如果有错误，只需要对出错的模块进行重新编译，无错的模块则不必再编译。因而可以
9、明显地节约整个程序的编译调试时间。用预处理命令#include可以包含有关文件的信息。#inlcude命令经过预处理命令（即在编译前进行的处理）后，会将其后有关文件的内容拷贝到命令所在的源程序文件中。该文件里包括常量的定义、结构的定义、函数原型的说明（即函数的返回类型、函数名以及函数参数类型的说明）等2.4详细设计算法思想算法一：存在的问题：图中可能存在回路，且图的任一顶点都可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点解决办法:为了避免重复访问，可设置一个标志顶点是否被访问过的辅助标志visitvex6/20辅助数组visitvex的初始状态为0，在图的遍历
10、过程中，一旦此顶点被访问，就立刻让visitvex为1，防止它被多次访问Visitevex0n-1的设置：图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visitvex0n-1，其初值为假，一旦访问了顶点Vi之后，便将visitvexi置为真。算法二：以邻接矩阵为存储结构的图的深度优先搜索遍历的算法voiddfs(Graph*g,intvex)intw;visitedvex=1;标记vex已被访问过visitvex(g,vex);访问图g的顶点for(w=firstadjvex
11、(g,vex);w0;w=nextadjvex(g,vex,w)if(!visitedw)dfs(g,w);从初始点vex出发广度优先搜索由邻接矩阵R表示的图voiddfstraverse(Graph*g)inti;for(i=1;ivexnum;i+)visitedi=0;7/20for(i=1;ivexnum;i+)if(!visitedi)dfs(g,i);算法三：以邻接矩阵为存储结构的图的广度优先搜索遍历的算法从初始点vex出发广度优先搜索由邻接矩阵R表示的图voidBESTraverse(Graph*g)inti;Que*q=(Que*)malloc(sizeof(Que);定义一个
12、队列q，其元素类型应为Que型for(i=1;ivexnum;i+)visitedi=0;标记初始点i未被已访问过initque(q);初始化队列for(i=1;ivexnum;i+)if(!visitedi)visitedi=1;标记初始点i已访问过visitvex(g,g-Vi);访问顶点ienque(q,g-Vi);将已访问过的初始点序号i入队while(!quempty(q)当队列非空时进行循环处理依次搜索i的每一个可能的邻接点intu,w;u=deque(q);8/20for(w=firstadjvex(g,u);w0;w=nextadjvex(g,u,w)if(!visitedw)
13、visitedw=1;访问一个未被访问过的邻接点visitvex(g,w);访问顶点wenque(q,w);顶点w出队三.用户手册:3.1运行环境本程序在windows环境下的VisualC+6.0的编译环境下执行。3.2执行文件四.测试数据及结果分析4.1.1调试过程中遇到的问题以及对设计与实现的回顾讨论和分析：一个图的DFS序列不一定惟一:当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之；源点和存储结构的内容均已确定的图的DFS序列惟一；邻接矩阵表示的图确定源点后，DFS序列惟一；DFS算法中，当从vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问
14、过的邻接点作为新的出发点，若这样的邻接点多于一个，则选中的总是序号较小的那一个。4.2运行结果五.调试报告:上机实验是对我们的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个环节。通常，我们在上机实验中遇到的问题比平时的习题复杂得多，也更接近实际,所以能从很大程度上提高我们的综合能力。一方9/20面，实验着眼于原理与应用的结合点，使我们学会如何把书上学到的知识用于解决实际的问题，从而培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握课堂上所讲授的内容的目的。通过这一次的课程设计，我们同学之间相互交流了许多的专业知识，在查阅文献资料时不知不觉中就学习到许多专业方面的知识，让我们学习到的知识得到了实践，而且同学之间的相互合作能力也得到加强。同时明白到在往后的学习当中，当编译程序遇到了错误的时候，不能慌乱，要认真阅读程序，找出错误，当错误无法排除的时候，要查阅各种文献，对于我们的程序调试有很大的帮助。附录:#include#include#defineINF32767/*INF表示*/typedefintInfoType;#defineMAXV100/*最大顶点个数*/#defineMAXQUE10/*队列的最大容量*/structnode/*图的顶点结构定义*/
