实验五 图的基本操作

实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容本次实验提供两个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其他选做！题目一：图的遍历（必做）[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。[测试数据]由学生依据软件工程的测试技术自己确定。题目二：在图G中求一条从顶点i到顶点s的简单路径[测试数据]自行设计题目三：在图G中求一条从顶点i到顶点s且长度为K的简单路径[测试数据]自行设计三、算法设计1、主要思想：首先定义邻接表存储结构，然后创建一个空队列，进行队列的进队，出对和判空操作，然后建立邻接表，接着进行图的深度优先遍历和广度遍历，最后编写主函数。对于邻接表，是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息。每个链表上附设一个表头结点。表结点：头结点：对于图的深度优先遍历DFS，类似于树的先根遍历，是树的先跟遍历的推广，是一个递归算法；对于图的广度优先遍历BFS，类似于树的层次遍历，不是递归算法。adjvexnextarcinfodatafirstarc2、本程序包含6个模块（1）主函数voidmain(){定义图，输出图的深度优先遍历和广度优先遍历结果；}（2）队列的构造：包括队列的初始化、进队、出对和判空，intInitQueue（）；intEnQueue（）；intDeQueue（）；intQueueEmpty（）。（3）邻接表的建立voidGreatGraph（）；（4）图的深度优先遍历voidDFS（）；（5）图的广度优先遍历voidBFS（）；3、元素类型和结点类型typedefstructArcNode{intadjvex;structArcNode*nextarc;intinfo;}ArcNode;typedefstructVNode{chardate;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;typedefstructQNode{chardata;structQNode*next;}QNode,*QueuePtr;typedefstruct{//构造一个空队列QueuePtrfront;QueuePtrrear;}LinkQueue;4、主函数和其他函数清单（1）intInitQueue（）：初始化队列；（2）intEnQueue（）：进队；（3）intDeQueue（）：出对；（4）intQueueEmpty（）：队列的判空（5）voidGreatGraph（）：建立邻接表；（6）voidDFS（）：深度优先遍历；（7）voidBFS（）：广度优先遍历；（8）voidmain（）：主函数。四、调试分析算法设计欠周全，在编写输出两条边的信息的时候，不能一次性输入完毕，必须得输入两个顶点后才能接着输入下一顶点信息，比较繁琐，不够简洁，如果顶点够多的话，比较花费时间；对输入的数据有了一定的考虑，如果输入的数据不合理，也就不能正确输出；刚开始时给数据赋初值有错，以后的多注意。五、实验结果利用课本第168页图7.13（a）图的数据进行测试六、总结对于这次实验，心里面一直很担心，因为实验都快做完了，我还一次都没有让老师检查过，然后时间上有特别的紧张，知道要做实验了，就一遍又一遍的去看书上相关的算法，上网查询，还有问了别的同学，最后才勉勉强强的将它给弄出来了。在让老师检查的时候，特别的紧张，话都说不利索了，很开心，但是还是有很多的不足之处，还是得好好的多看书，把基础知识给弄透彻。我争取下次还把实验给做出来。七、源程序#includeiostream.h#includestdio.h#includestdlib.h#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode*nextarc;intinfo;}ArcNode;typedefstructVNode{chardate;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;typedefstructQNode{chardata;structQNode*next;}QNode,*QueuePtr;typedefstruct{//构造一个空队列QueuePtrfront;QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q){Q.front=Q.rear=newQNode;if(!Q.front)exit(-1);Q.front-next=NULL;return0;}intEnQueue(LinkQueue&Q,inte){QueuePtrp;p=newQNode;if(!p)exit(-1);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return0;}intDeQueue(LinkQueue&Q,int&e){QueuePtrp;if(Q.front==Q.rear)return0;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);return0;}intQueueEmpty(LinkQueue&Q){if(Q.front==Q.rear)return1;elsereturn0;}intLocatevex(ALGraph&G,charv){intk,j=0;for(k=0;kG.vexnum;k++)if(G.vertices[k].date==v){j=k;break;}returnj;}voidGreatGraph(ALGraph&G)//建立邻接表{intk;chartail,head;inti,j;cout输入顶点数和弧数endl;cinG.vexnumG.arcnum;cout输入顶点信息endl;for(i=0;iG.vexnum;i++){cinG.vertices[i].date;G.vertices[i].firstarc=NULL;}cout输入边的信息：endl;for(k=0;kG.arcnum;k++){cout输入两条边的信息endl;cintailhead;j=Locatevex(G,head);i=Locatevex(G,tail);ArcNode*p=newArcNode;p-adjvex=j;p-nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;ArcNode*q=newArcNode;q-adjvex=i;q-nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=q;}}intFirstAdjVex(ALGraphG,intv){//返回v的第一个邻接顶点if(G.vertices[v].firstarc)returnG.vertices[v].firstarc-adjvex;elsereturn-1;}intNextAdjVex(ALGraphG,intv,intw){//返回v中相对于w的下一个邻接顶点intflag=0;ArcNode*p;p=G.vertices[v].firstarc;while(p){if(p-adjvex==w){flag=1;break;}p=p-nextarc;}if(flag&&p-nextarc)returnp-nextarc-adjvex;elsereturn-1;}//深度优先遍历intvisited[30];voidDFS(ALGraph&G,intv){visited[v]=1;coutG.vertices[v].dateendl;intw;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)){if(!visited[w])DFS(G,w);}}voidDFSTraverse(ALGraph&G){intv;for(v=0;vG.vexnum;++v)visited[v]=0;for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);}int(*visit)(intv);voidBFS(ALGraph&G)//广度优先遍历{intv;LinkQueueQ;intw;for(v=0;vG.vexnum;++v)visited[v]=0;InitQueue(Q);for(v=0;vG.vexnum;++v)if(!visited[v]){visited[v]=1;coutG.vertices[v].dateendl;EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,v);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!visited[w]){visited[w]=1;coutG.vertices[w].dateendl;EnQueue(Q,w);}}}}voidmain(){ALGraphG;GreatGraph(G);cout深度优先遍历序列为：endl;DFSTraverse(G);cout广度优先遍历序列为：endl;BFS(G);}