图的遍历数据结构实验报告.doc

《图的遍历数据结构实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南昌航空大学实验报告课程名称：数据结构实验名称：实验八图的遍历班级：学生姓名：学号：指导教师评定：签名:题目：假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。一、需求分析1.用户可以根据自己的需求分别输入任意的一个有向图<可以是非连通图也可以是连通图）。2.通过用广度优先遍历和深度优先遍历已有的图，并输出。3.并且以邻接表的形式输出该已有的图。4.程序执行的命令包括：<1）输入图的结点和弧构造图<2）输出图<2）广度优先遍历图<3）深度优先遍历图二、概要设计⒈为实现上述算法，需要链表的抽象数

2、据类型：ADTGraph{数据对象V：V是具有相同特征的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={

3、v,w∈V且P表示从x到w的弧，谓词P的意义或信息}b5E2RGbCAP基本操作P:Creatgraph(&G,V,VR>初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。destroygraph(&G>初始条件：图G存在。操作结果：销毁图G。displaygraph

4、atevex(G,u>初始条件：图G存在，u和G中的顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其他信息。getvex(G,v>初始条件：图G存在，v是G中的某个顶点。13/13操作结果：返回v的值。DFStraverse(G>初始条件：图G存在。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一次。BFStraverse(&S,e>初始条件：图G存在。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一次。}ADTGraph2.本程序有三个模块：⑴主程序模块main(>{

5、初始化；{接受命令；显示结果；｝｝⑵创建图的模块：主要建立一个图；⑶广度优先遍历和深度优先遍历模块：输出这两种遍历的结果；(4>输出图模块：显示已创建的图。三、详细设计⒈元素类型，结点类型structarcnode{intadjvex。/*该弧所指向的顶点的位置*/intinfo。structarcnode*nextarc。/*指向下一条弧的指针*/}。structvexnode{intdata。/*顶点的信息*/structarcnode*firstarc。/*指向第一条依附该顶点的弧的指针*/}。structgraph{

6、structvexnode*vexpex。intvexnum,arcnum。/*图的当前的顶点数和弧数*/}；/*定义队列*/structqueue{int*elem。intfront。13/13intrear。}。/*全局变量*/intn。/*图的顶点数*/intvisit[100]。/*标志数组*/structqueueQ。2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创建一个空队列*/structqueueinitqueue(>{structqueueq。q.elem=(int*>malloc(maxsize*

7、sizeof(int>>。if(!q.elem>exit(0>。q.front=q.rear=0。returnq。}/*入队列*/structqueueenqueue(structqueueq,intv>{if((q.rear+1>%maxsize==q.front>printf("thequeueisfull！！！">。else{q.elem[q.rear]=v。q.rear=(q.rear+1>%maxsize。}returnq。}/*出队列*/intdequeue(structqueueq>{intcur。if(q

8、.rear==q.front>{printf("thequeueisnull!!">。exit(0>。}else{cur=q.elem[q.front]。q.front=(q.front+1>%maxsize。returncur。}}/*判断队列是否为空*/intemptyqueue(structqueueq>{if(q.front==q.rear>return1。elsereturn0。13/13}/*创建有向图*/structgraphcreatgraph(>{inte,i,s,d。inta。structgraphg

9、。structarcnode*p。printf("thenumberofvex(n>andarc(e>:">。scanf("%d%d",&n,&e>。g.vexnum=n。g.arcnum=e。for(i=0。i{printf("di%dvex'sinforma