《数据结构》图的遍历

1衡阳师范学院《数据结构》课程设计题目：图的遍历班级：计算机科学系0902班学号：091902300919021009190202作者姓名：徐森枝黎邦举陈哲峰指导教师：王樱老师2010年12月28日2目录1、需求分析………………………………………………………………（3）1．1问题描述………………………………………………………（3）1．2基本要求………………………………………………………（3）1.3图的遍历介绍…………………………………………………（3）2、概要设计………………………………………………………………（5）2．1算法说明……………………………………………………（5）2．2算法分析……………………………………………………（6）2.3程序分析……………………………………………………（9）3、详细设计……………………………………………………………（10）4、调试与分析…………………………………………………………（18）4．1调试分析……………………………………………………（18）4．2运行结果……………………………………………………（24）5、用户手册……………………………………………………………（24）5．1运行环境……………………………………………………（24）5．2执行文件……………………………………………………（24）6、参考文献………………………………………………………………（25）7、心得体会………………………………………………………………（25）8、小组成员任务分配及工作进度安排…………………………………（25）31.需求分析1.1问题描述从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。试编写一个程序，完成对图的遍历。1.2基本要求1．以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。2．分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。1.3图的遍历介绍1.3.1、基本概念图的遍历:图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。1.3.2、分类按照搜索途径的不同，图的遍历可分为：深度优先遍历（Depth-FirstTraverse）和广度优先遍历（Breadth-FirstTraverse）两大类。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。（1）深度优先遍历(Depth-FirstTraverse)4特点：尽可能先对纵深方向的顶点进行访问①．深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。②.深度优先搜索的过程a基本思想:首先访问图中某一个指定的出发点Vi；然后任选一个与顶点Vi相邻的未被访问过的顶点Vj；以Vj为新的出发点继续进行深度优先搜索，直至图中所有顶点均被访问过。b具体过程:设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。(2)广度优先遍历（Breadth-FirstTraverse）:5特点：尽可能先从指定的出发点，横向地访问图中各个顶点。①．广度优先遍历的定义在访问了起始点之后,首先依次访问起始点的各个邻接点,然后依次访问那些顶点中未被访问过的邻接点.依此类推,直到所有被访问到的顶点的邻接点都被访问过为止.②．广度优先搜索的过程a算法基本思想：首先访问图中某一指定的出发点Vi；然后依次访问Vi的所有接点Vi1，Vi2…Vit；再次访问Vi1，Vi2…，Vit的邻接点中未经访问过的顶点，依此类推，直到图中所有顶点均被访问为止。b具体过程：从广度优先搜索遍历方法可知，先被访问的顶点的邻接点也被访问，即假设顶点V在W之前被访问，那么顶点V的所有未经访问的邻接点也在顶点W的所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一个队列结构，用以保存已访问过的顶点的序号，访问该顶点的所有未经访问的顶点。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样会出现回退的现象。因此它不是个递归的过程。为了实现逐层访问，算法中使用了一个队列以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为了避免重复访问，需要一个辅助函数visitvex[]给被访问过的顶点加标记。2.概要设计2.1算法说明数据类型及函数定义定义图typedefstruct{intV[M];intR[M][M];6intvexnum;}Graph;创建图voidcreatgraph(Graph*g,intn)打印图的邻接矩阵voidprintgraph(Graph*g)访问顶点voidvisitvex(Graph*g,intvex)深度递归遍历voiddfs(Graph*g,intvex)队列的基本操作定义队列typedefstruct{intV[M];intfront;intrear;}Queue;判断队列是否为空quempty(Queue*q)入队操作enqueue(Queue*q,inte)出队操作dequeue(Queue*q)广度遍历voidBESTraverse(Graph*g)本程序包含四个模块：主程序模块voidmain(){构造一个图；打印图的邻接矩阵7进行深度优先遍历图；进行广度优先遍历图；}；2.2算法分析算法一：存在的问题：图中可能存在回路，且图的任一顶点都可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点解决办法:为了避免重复访问，可设置一个标志顶点是否被访问过的辅助标志visitvex辅助数组visitvex的初始状态为0，在图的遍历过程中，一旦此顶点被访问，就立刻让visitvex为1，防止它被多次访问Visitevex[0．．n-1]的设置：图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visitvex[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visitvex[i]置为真。流程图如下：8算法二：以邻接矩阵为存储结构的图的深度优先搜索遍历的算法voiddfs(Graph*g,intvex){intw;visited[vex]=1;标记vex已被访问过visitvex(g,vex);访问图g的顶点for(w=firstadjvex(g,vex);w0;w=nextadjvex(g,vex,w))if(!visited[w]){dfs(g,w);}}从初始点vex出发广度优先搜索由邻接矩阵R表示的图voiddfstraverse(Graph*g)9{inti;for(i=1;i=g-vexnum;i++)visited[i]=0;for(i=1;i=g-vexnum;i++)if(!visited[i]){dfs(g,i);}}算法三：以邻接矩阵为存储结构的图的广度优先搜索遍历的算法从初始点vex出发广度优先搜索由邻接矩阵R表示的图voidBESTraverse(Graph*g){inti;Queue*q=(Queue*)malloc(sizeof(Queue));定义一个队列q，其元素类型应为Queue型for(i=1;i=g-vexnum;i++){visited[i]=0;标记初始点i未被已访问过}initqueue(q);初始化队列for(i=1;i=g-vexnum;i++){if(!visited[i]){visited[i]=1;标记初始点i已访问过visitvex(g,g-V[i]);访问顶点ienqueue(q,g-V[i]);将已访问过的初始点序号i入队while(!quempty(q))当队列非空时进行循环处理{依次搜索i的每一个可能的邻接点intu,w;u=dequeue(q);10for(w=firstadjvex(g,u);w0;w=nextadjvex(g,u,w)){if(!visited[w]){visited[w]=1;访问一个未被访问过的邻接点visitvex(g,w);访问顶点wenqueue(q,w);顶点w出队}}}}}}2.3程序分析本程序划分为三个不同的模块分别编译。其优点在于编译时如果有错误，只需要对出错的模块进行重新编译，无错的模块则不必再编译。因而可以明显地节约整个程序的编译调试时间。用预处理命令#include可以包含有关文件的信息。#inlcude命令经过预处理命令（即在编译前进行的处理）后，会将其后有关文件的内容拷贝到命令所在的源程序文件中。该文件里包括常量的定义、结构的定义、函数原型的说明（即函数的返回类型、函数名以及函数参数类型的说明）等3.详细设计#defineM20#includestdio.h#includestdlib.h#includemalloc.h/*定义图*/11typedefstruct{intV[M];intR[M][M];intvexnum;}Graph;/*创建图*/voidcreatgraph(Graph*g,intn){inti,j,r1,r2;g-vexnum=n;/*顶点用i表示*/for(i=1;i=n;i++){g-V[i]=i;}/*初始化R*/for(i=1;i=n;i++)for(j=1;j=n;j++){g-R[i][j]=0;}/*输入R*/printf(PleaseinputR(0,0END):\n);scanf(%d,%d,&r1,&r2);while(r1!=0&&r2!=0){g-R[r1][r2]=1;g-R[r2][r1]=1;scanf(%d,%d,&r1,&r2);}}12/*打印图的邻接矩阵*/voidprintgraph(Graph*g){inti,j;for(i=1;i=g-vexnum;i++){for(j=1;j=g-vexnum;j++){printf(%2d,g-R[i][j]);}printf(\n);}}/*全局变量：访问标志数组*/intvisited