实验五 图的遍历

[键入文字]中原工学院数据结构实验报告软件111-2011008341021实验五图的基本操作一、实验目的与内容1.实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。2.实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。[测试数据]由学生依据软件工程的测试技术自己确定。二．程序设计1.总体设计#includeiostream.h#defineMaxVerNum20structEdgenode{intedgever;//该弧所指向的的顶点的信息intinform;//该边的信息Edgenode*edgenext;//指向下一条边的指针};structVexnode{charvertex;Edgenode*firstarc;};structGraph{VexnodeAdjList[MaxVerNum];intvexnum,arcnum;//图的当前顶点数和弧数};//队列的定义及相关函数的实现[键入文字]中原工学院数据结构实验报告软件111-2011008341022structQueueNode{intnData;QueueNode*next;};structQueueNode{QueueNode*front;QueueNode*rear;};voidEnQueue(QueueList*Q,inte);//进队操作voidDeQueue(QueueList*Q,int*e);//出队操作voidCreatAdjList(Graph*G);//创建图voidDFS(Graph*G,inti,intvisit[]);//从第i个顶点出发递归的深度优先遍历图GvoidDFStraversal(Graph*G,charc);//对图G作深度优先遍历voidBFS(Graph*G,intv,intvisit[]);//从第v个顶点出发递归的广度优先遍历图GvoidBFStraversal(Graph*G,charc);//对图G作广度优先遍历2.详细设计定义结构体QueueNode、QueueNode，并完成队列的基本操作，利用队列先进先出的性质，在广度优先遍历时将队列作为辅助工具来完成广度优先遍历。voidEnQueue(QueueList*Q,inte)函数实现进队操作，if-else语句完成函数的具体操作voidDeQueue(QueueList*Q,int*e)函数实现出队操作，if-else语句完成函数的具体操作voidCreatAdjList(Graph*G)函数用来完成创建图的操作，其中使用两次for循环语句第一次用循环语句输入顶点，第二次建立无向图中的边和表，流程图如图表1所示voidDFS(Graph*G,inti,intvisit[])函数是从第i个顶点出发递归的深度优先遍历图G[键入文字]中原工学院数据结构实验报告软件111-2011008341023图表1voidDFStraversal(Graph*G,charc)函数对图G作深度优先遍历，首先用for循环语句初始化辅助数组，且全部初始化为0，表示的状态为未访问。其次，用for循环语句根据字符查找序号，调用DFS()函数从第i个顶点出发递归的广度优先，流程图如图表2所示。最后再次使用for循环语句继续访问未被访问的结点，流程图如图表3所示k=0kG-arcnumcout请输入边Vi,Vj对应的顶点:;cinij;p1=newEdgenode;p1-edgever=j;p1-edgenext=G-AdjList[i].firstarc;G-AdjList[i].firstarc=p1;p2=newEdgenode;p2-edgever=i;p2-edgenext=G-AdjList[j].firstarc;G-AdjList[j].firstarc=p2;truek++[键入文字]中原工学院数据结构实验报告软件111-2011008341024图表2图表3truei=0iG-arcnumif(G-AdjList[i].vertex==c){m=i;DFS(G,i,visit);break;}i++i=0iG-arcnumif(visit[i]==0)DFS(G,i,visit);i++[键入文字]中原工学院数据结构实验报告软件111-2011008341025voidBFS(Graph*G,intv,intvisit[])函数从第v个顶点出发递归的广度优先遍历图G，使用辅助队列Q变量，在此函数中完成进队、出对操作。还定义一个visit[]数组，用来标记顶点是否被访问过。在while循环进行相关的入队和出队操作，if-else循环进行将没有访问过的顶点入队图表4voidBFStraversal(Graph*G,charc)函数对图G作广度优先遍历，使用辅助数组visited[],且初始化为0，表示未访问过，在函数中调用BFS()，来完成相关操作3.调试及解决问题测试数据为书上168页的图7.13上的数据。只是把vi改成了a-h，顶点数为8，边数为9Q-rear!=NULLinte=0;DeQueue(Q,&e);coutG-AdjList[e].vertex;visit[e]=1;Edgenode*p=newEdgenode;p=G-AdjList[e].firstarc;if(p){intm=p-edgever;if(m==0){EnQueue(Q,m);while(visit[m]==0){p=p-edgenext;break;m=p-edgever;EnQueue(Q,m);}}}truefalse[键入文字]中原工学院数据结构实验报告软件111-2011008341026图表5输入边的信息图表64.测试代码//main()函数intmain(){Graph*G=newGraph;CreatAdjList(G);//调用CreatAdjList()函数，创建图charch;cout请输入开始遍历的顶点:;cinch;DFStraversal(G,ch);//深度优先遍历图BFStraversal(G,ch);//广度优先遍历图return0;}三．源代码voidEnQueue(QueueList*Q,inte)//进队操作[键入文字]中原工学院数据结构实验报告软件111-2011008341027{QueueNode*q=newQueueNode;q-nData=e;q-next=NULL;if(Q==NULL)return;if(Q-rear==NULL)Q-front=Q-rear=q;else{Q-rear-next=q;Q-rear=Q-rear-next;}}voidDeQueue(QueueList*Q,int*e)//出队操作{if(Q==NULL)return;if(Q-front==Q-rear){*e=Q-front-nData;Q-front=Q-rear=NULL;}else{*e=Q-front-nData;Q-front=Q-front-next;}}voidCreatAdjList(Graph*G)//创建图{inti,j,k;Edgenode*p1;Edgenode*p2;cout请输入顶点数和边数:endl;cinG-vexnumG-arcnum;//输入顶点数和边数cout开始输入顶点输入顶点表:endl;for(i=0;iG-vexnum;i++){cinG-AdjList[i].vertex;//输入顶点G-AdjList[i].firstarc=NULL;}cout开始输入边表信息:endl;[键入文字]中原工学院数据结构实验报告软件111-2011008341028for(k=0;kG-arcnum;k++){//因为是无向图，所以有两次建立边表的过程cout请输入边Vi,Vj对应的顶点:;cinij;p1=newEdgenode;p1-edgever=j;p1-edgenext=G-AdjList[i].firstarc;G-AdjList[i].firstarc=p1;p2=newEdgenode;p2-edgever=i;p2-edgenext=G-AdjList[j].firstarc;G-AdjList[j].firstarc=p2;}}//-------------------------------------------------------------voidDFS(Graph*G,inti,intvisit[])//从第i个顶点出发递归的深度优先遍历图G{coutG-AdjList[i].vertex;visit[i]=1;Edgenode*p=newEdgenode;p=G-AdjList[i].firstarc;if(G-AdjList[i].firstarc&&!visit[p-edgever]){DFS(G,p-edgever,visit);}}voidDFStraversal(Graph*G,charc)//对图G作深度优先遍历{cout该图的深度优先遍历结果为:endl;intvisit[MaxVerNum];for(inti=0;iG-vexnum;i++){visit[i]=0;//初始化辅助数组，全部初始化为0，即未访问状态}intm;for(i=0;iG-vexnum;i++){if(G-AdjList[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);//从第i个顶点出发递归的广度优先遍历图Gbreak;[键入文字]中原工学院数据结构实验报告软件111-2011008341029}}for(i=0;iG-vexnum;i++)//继续访问未被访问的结点{if(visit[i]==0)DFS(G,i,visit);//从第i个顶点出发递归的广度优先遍历图G}coutendl;}voidBFS(Graph*G,intv,intvisit[])//从第v个顶点出发递归的广度优先遍历图G{QueueList*Q=newQueueList;//定义辅助队列Q变量Q-front=Q-rear=NULL;//队列进行初始化EnQueue(Q,v);//图中的顶点作为数据进队while(Q-rear!=NULL){inte=0;DeQueue(Q,&e);//出队coutG-AdjList[e].vertex;visit[e]=1;//标记vi已经访问过Edgenode*p=newEdgenode;p=G-AdjList[e].firstarc;if(p)//此次搜索ve的邻接点{intm=p-edgever;if(m==0){EnQueue(Q,m);//入队while(visit[m]==0)//未访问过{p=p-edgenext;//找下一邻接点if(p==NULL)break;m=p-edgever;EnQueue(Q,m);//入队}}}}}voidBFStraversal(Graph*G,charc)//对图G作广度优先遍历[键入文字]中原工学院数据结构实验报告软件111-20110083410210{cout该图的广度优先遍历结果为:endl;intvisited[MaxVerNum];//辅助数组for(inti=0;iG-vexnum;i++)//初始化辅助数组，表示未访问过{visited[i]=0;}intm;for(