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

《图的遍历1数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、，称为顶点集。数据关系R：R={VR}VR={

3、v,w∈V且P（v,w），表示从x到w的弧，谓词P（v,w）定义了弧的意义或信息}基本操作P:Creatgraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。destroygraph(&G)初始条件：图G存在。操作结果：销毁图G。displaygraph（G）初始条件：图G存在。操作结果：显示图G。locatevex(G,u)初始条件：图G存在，u和G中的顶点有相同的特征。12操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其他信息。getvex(G

4、,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的值。DFStraverse(G)初始条件：图G存在。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一次。BFStraverse(&S,e)初始条件：图G存在。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一次。}ADTGraph2.本程序有三个模块：⑴主程序模块main(){初始化；{接受命令；显示结果；｝｝⑵创建图的模块：主要建立一个图；⑶广度优先遍历和深度优先遍历模块：输出这两种遍历的结果；(4)输出图模块：显示已创建的图。三、详细设计⒈元素类型，结点类型structarcnode{intadjvex;

5、/*该弧所指向的顶点的位置*/intinfo;structarcnode*nextarc;/*指向下一条弧的指针*/};structvexnode{intdata;/*顶点的信息*/structarcnode*firstarc;/*指向第一条依附该顶点的弧的指针*/};structgraph{structvexnode*vexpex;intvexnum,arcnum;/*图的当前的顶点数和弧数*/}；/*定义队列*/structqueue{12int*elem;intfront;intrear;};/*全局变量*/intn;/*图的顶点数*/intvisit[100];/*标志数组*/stru

6、ctqueueQ;2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创建一个空队列*/structqueueinitqueue(){structqueueq;q.elem=(int*)malloc(maxsize*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.rea

7、r=(q.rear+1)%maxsize;}returnq;}/*出队列*/intdequeue(structqueueq){intcur;if(q.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;12elsereturn0;}/*创建有向图*/structgraphcreat

8、graph(){inte,i,s,d;inta;structgraphg;structarcnode*p;printf("thenumberofvex(n)andarc(e):");scanf("%d%d",&n,&e);g.vexnum=n;g.arcnum=e;for(i=0;i