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

南昌航空大学实验报告课程名称：数据结构实验名称：实验八图的遍历班级：学生姓名：学号：指导教师评定：签名:题目：假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。需求分析用户可以根据自己的需求进行输入所需的图（可以是非连通图也可以是连通图），其中1表示创建一个有向图，2表示创建一个无向图。用户进入菜单页面选择输入图的状态（1表示创建一个有向图，2表示创建一个无向图，3表示输出已创建的图，4表示深度优先遍历已有的图，5表示广度优先遍历已有的图，6表示退出程序状态）。程序执行的命令包括：（1）输入图的结点和弧构造图（2）输出图（2）广度优先遍历图（3）深度优先遍历图二、概要设计⒈为实现上述算法，需要链表的抽象数据类型：ADTGraph{数据对象V：V是具有相同特征的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={<v,w>|v,w∈V且P（v,w），<v,w>表示从x到w的弧，谓词P（v,w）定义了弧<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中的顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其他信息。getvex(G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的值。DFStraverse(G)初始条件：图G存在。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一次。BFStraverse(&S,e)初始条件：图G存在。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一次。}ADTGraph2.本程序有三个模块：⑴主程序模块main(){初始化；Switch（参数）{Case1：接受命令（用户创建一个有向图）；Case2：接受命令（用户创建一个无向图）；Case3：接受命令（输出已创建的图）；Case4：接受命令（深度优先遍历已有的图）；Case5：接受命令（广度优先遍历已有的图）；Case6：接受命令（退出程序）；｝｝⑵创建图的模块：主要建立一个图；⑶广度优先遍历和深度优先遍历模块：输出这两种遍历的结果；(4)输出图模块：显示已创建的图。三、详细设计⒈元素类型，结点类型structarcnode{intadjvex;/*该弧所指向的顶点的位置*/intinfo;structarcnode*nextarc;/*指向下一条弧的指针*/};structvexnode{intdata;/*顶点的信息*/structarcnode*firstarc;/*指向第一条依附该顶点的弧的指针*/};structgraph{structvexnode*vexpex;intvexnum,arcnum;/*图的当前的顶点数和弧数*/}；/*定义队列*/structqueue{int*elem;intfront;intrear;};/*全局变量*/intn;/*图的顶点数*/intvisit[100];/*标志数组*/structqueueQ;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！！！\n");else{q.elem[q.rear]=v;q.rear=(q.rear+1)%maxsize;}returnq;}/*出队列*/intdequeue(structqueueq){intcur;if(q.rear==q.front){printf("thequeueisnull!!\n");exit(0);}else{cur=q.elem[q.front];q.front=(q.front+1)%maxsize;returncur;}}/*判断队列是否为空*/intemptyqueue(structqueueq){if(q.front==q.rear)return1;elsereturn0;}/*创建有向图*/structgraphcreatgraph1(){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<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;}returng;}/*创建无向图*/structgraphcreatgraph2(){inte,i,s,d;inta;structgraphg;structarcnode*p,*q;printf("thenumberofvex(n)andarc(e):");scanf("%d%d",&n,&e);g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;q=(structarcnode*)malloc(sizeof(structarcnode));q->adjvex=s;q->info=g.vexpex[s].data;q->nextarc=g.vexpex[d].firstarc;g.vexpex[d].firstarc=q;}returng;}/*显示有向图*/voiddisplaygraph(structgraphg,intn){inti;structarcnode*p;printf("diaplaythegraph;\n");for(i=0;i<n;i++){printf("[%d,%d]->",i,g.vexpex[i].data);p=g.vexpex[i].firstarc;while(p!=NULL){printf("(%d,%d)->",p->adjvex,p->info);p=p->nextarc;}printf("^\n");}}/*连通图广度优先遍历*/voidBFSsearch(structgraphg,intv){inti;structarcnode*p;Q=initqueue();printf("%5d",g.vexpex[v].data);enqueue(Q,v);visit[v]=TURE;while(!emptyqueue(Q)){i=dequeue(Q);p=g.vexpex[i].firstarc;while(p!=NULL){enqueue(Q,p->adjvex);if(visit[p->adjvex]==FALSE){printf("%5d",p->info);visit[p->adjvex]=TURE;}p=p->nextarc;}}}/*非连通图广度优先遍历*/voidBFS(structgraphg){inti;printf("BFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)if(visit[i]==FALSE)BFSsearch(g,i);printf("\n\n");}/*连通图深度优先遍历*/voidDFSsearch(structgraphg,intv){structarcnode*p;printf("%5d",g.vexpex[v].data);visit[v]=TURE;p=g.vexpex[v].firstarc;while(p!=NULL){if(!visit[p->adjvex])DFSsearch(g,p->adjvex);p=p->nextarc;}}/*非连通图深度优先遍历*/voidDFS(structgraphg){inti;printf("DFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)if(visit[i]==FALSE)DFSsearch(g,i);printf("\n\n");}/*主菜单定义*/intmenu_select(){chars[80];intc;gotoxy(1,25);/*将光标定在第25行第1列*/printf("pressanykeyentermenu\n");/*提示按任意键继续*/getch();/*读入任意字符*/clrscr();/*清屏*/gotoxy(1,1);printf("***************MENU***************\n\n");printf("1.Makeadigraphbyyouself!\n");printf("2.Makeaundigraphbyyouself!\n");printf("3.Ontputyourgraph!\n");printf("4.Depth_firstsearchyourgraph!\n");printf("5.Bredth_firstsearchyourgraph!\n");printf("6.Quit!\n");printf("**********************************\n");do{printf("\nEnteryouchoice(1~6):\n");/*提示输入选项*/scanf("%s",s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整型*/}while(c<1||c>6);returnc;}3.主函数和其他函数的伪码算法voidmain(){structgraphg;inti;clrscr();/*清屏*/for(;;){switch(menu_select()){case1:{clrscr();g=creatgraph1();break;}case2:{clrscr();g=creatgraph2();break;}case3:{clrscr();printf("diaplaythegraph;\n");displaygraph(g,n);break;}case4:{clrscr();printf("DFSresult:\n");DFS(g);break;}case5:{clrscr();printf("BFSresult:\n");BFS(g);break;}case6:exit(0);}}}4函数调用关系maincreatgraphdisplaygraphBFSDFSBFSsearchDFSsearch initqueuedequeueenqueue四、调试分析⒈本来想将图的顶点元素的类型定义为字符型的，但是在运行的时候发现在输入顶点数和弧数后，总是会在有字符没有输入就直接运行下一个语句了，改变了很多的方法，最后只有将顶点的类型定义为才解决了上述的问题。⒉在写程序的时候，开始creatgraph函数的部分代码为for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}g.vexnum=n;g.arcnum=e;总是会有这样的提示“可能在‘g’定义以前已经使用了在creatgraph函数中”，经过多次的调试，最后代码改为g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}就解决了问题，但是我还是不清楚原因。3.在编写BFSsearch函数的时候，用指针入队还是用下标值入队，由于对指针的掌握不够，最后选择了比较容易的用下标值作为队列的类型int。4.在调试的时候，选择选项3、4、5的时候总是没有执行printf语句，最后分别在主函数和要调用的函数中都加上同一printf语句就解决了问题，能够显示printf中的信息。5.算法的时空分析 各操作的算法时间复杂度比较合理 initqueue，emptyqueue，enqueue，dequeue，visit为O(1)；creatgraph，displaygraph1，displaygraph2BFSsearch，DFS，DFSsearch，BFS为O(n),注：n为图的顶点数。6.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册⒈本程序的运行环境为windowsxp操作系统，并且在TC2.0中运行，执行文件为Exp8.c；⒉.在输入有向图的信息的时候，注意输入的顺序，这关系到顶点的位置，否则就会与你想要的图就不一样了。如你的图为18222021若你输入的顶点的顺序是20,18，21，22则它们对应的数值的下标为0,1,2，3。因此表示的弧（起点，终点）就应该为（0,2），（1,0），（2,1），（3,0），（3,2），但是弧输入的顺序没有要求。而创建无向图的时候就没有这个要求了，只要输入能表示该边的两个正确的端点即可。3.按任意键进入主菜单如图：注：1：表示创建一个有向图；2：表示创建一个无向图；3：表示输出已创建的图；4：表示深度优先遍历已有的图；5：表示广度优先遍历已有的图；6：表示退出程序状态。4.进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS环境中，用户根据需求键入相应的数据，可以看到相应的结果。六、测试结果若想创建一个无向图（在主菜单选择2）在主菜单选择2输入的图如图所示：按任意键进入主菜单选择3，输出图为：按任意键进入主菜单选择4，输出DFS的结果：按任意键进入主菜单选择5，输出BFS的结果:按任意键进入主菜单选择6，退出程序。七、附录：源程序#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>#include<ctype.h>#defineNULL0#defineFALSE0#defineTURE1#definemaxsize100structarcnode{intadjvex;/*该弧所指向的顶点的位置*/intinfo;structarcnode*nextarc;/*指向下一条弧的指针*/};structvexnode{intdata;/*顶点的信息*/structarcnode*firstarc;/*指向第一条依附该顶点的弧的指针*/};structgraph{structvexnode*vexpex;intvexnum,arcnum;/*图的当前的顶点数和弧数*/};/*定义队列*/structqueue{int*elem;intfront;intrear;};intn;/*图的顶点数*/intvisit[100];/*标志数组*/structqueueQ;/*创建一个空队列*/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！！！\n");else{q.elem[q.rear]=v;q.rear=(q.rear+1)%maxsize;}returnq;}/*出队列*/intdequeue(structqueueq){intcur;if(q.rear==q.front){printf("thequeueisnull!!\n");exit(0);}else{cur=q.elem[q.front];q.front=(q.front+1)%maxsize;returncur;}}/*判断队列是否为空*/intemptyqueue(structqueueq){if(q.front==q.rear)return1;elsereturn0;}/*创建有向图*/structgraphcreatgraph1(){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<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;}returng;}/*创建无向图*/structgraphcreatgraph2(){inte,i,s,d;inta;structgraphg;structarcnode*p,*q;printf("thenumberofvex(n)andarc(e):");scanf("%d%d",&n,&e);g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;q=(structarcnode*)malloc(sizeof(structarcnode));q->adjvex=s;q->info=g.vexpex[s].data;q->nextarc=g.vexpex[d].firstarc;g.vexpex[d].firstarc=q;}returng;}/*显示图*/voiddisplaygraph(structgraphg,intn){inti;structarcnode*p;printf("diaplaythegraph;\n");for(i=0;i<n;i++){printf("[%d,%d]->",i,g.vexpex[i].data);p=g.vexpex[i].firstarc;while(p!=NULL){printf("(%d,%d)->",p->adjvex,p->info);p=p->nextarc;}printf("^\n");}}/*连通图广度优先遍历*/voidBFSsearch(structgraphg,intv){inti;structarcnode*p;Q=initqueue();printf("%5d",g.vexpex[v].data);enqueue(Q,v);visit[v]=TURE;while(!emptyqueue(Q)){i=dequeue(Q);p=g.vexpex[i].firstarc;while(p!=NULL){enqueue(Q,p->adjvex);if(visit[p->adjvex]==FALSE){printf("%5d",p->info);visit[p->adjvex]=TURE;}p=p->nextarc;}}}/*非连通图广度优先遍历*/voidBFS(structgraphg){inti;printf("BFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)if(visit[i]==FALSE)BFSsearch(g,i);printf("\n\n");}/*连通图深度优先遍历*/voidDFSsearch(structgraphg,intv){structarcnode*p;printf("%5d",g.vexpex[v].data);visit[v]=TURE;p=g.vexpex[v].firstarc;while(p!=NULL){if(!visit[p->adjvex])DFSsearch(g,p->adjvex);p=p->nextarc;}}voidDFS(structgraphg)/*非连通图深度优先遍历*/{inti;printf("DFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)