实验五 图的基本操作

实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】由学生依据软件工程的测试技术自己确定。三.算法设计1、主要思想：图的深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有定点未曾被访问，则深度优先搜索可以从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先搜索遍历此图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问为止，所使用的为递归算法。图的广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某定点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的定点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问为止，过程需要使用数组，非递归。2、本程序包含三个模块1）创建图voidCreatAdjList(Graph*G)2）深度优先搜索遍历voidDFS(Graph*G,inti,intvisit[])3）广度优先搜索遍历voidBFS(Graph*G,intv,intvisit[])voidBFStraversal(Graph*G,charc)四.调试分析1.在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志程已被访问，就不再从它出发进行搜索。2.遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间取决于所采用的存储结构。3.深度优先搜索遍历的时间复杂度和广度优先搜索遍历相同，两者不同之处仅仅在于对顶点的访问顺序不同。五.实验结果构造图，输入关于图的数据，进行遍历的顶点开始深度优先搜索遍历和广度优先搜索遍历五、总结这次实验让我深刻的理解了用邻接表做存储结构时怎么构造无向图,以及图的两种遍历方式是怎么实现,本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。对于深度优先遍历,主要是采用递归的方式,广度优先遍历借助队列来实现。七.源程序（带注释）#includeiostreamusingnamespacestd;#defineMaxVerNum50structedgenode{intendver;intinform;edgenode*edgenext;};structvexnode{charvertex;edgenode*edgelink;};structGraph{vexnodeadjlists[MaxVerNum];intvexnum;intarcnum;};//队列的定义及相关函数的实现structQueueNode{intnData;QueueNode*next;};structQueueList{QueueNode*front;QueueNode*rear;};voidEnQueue(QueueList*Q,inte){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-adjlists[i].vertex;G-adjlists[i].edgelink=NULL;}cout开始输入边表信息:endl;for(k=0;kG-arcnum;k++){cout请输入边Vi,Vj对应的顶点:;cinij;p1=newedgenode;p1-endver=j;p1-edgenext=G-adjlists[i].edgelink;G-adjlists[i].edgelink=p1;p2=newedgenode;p2-endver=i;p2-edgenext=G-adjlists[j].edgelink;G-adjlists[j].edgelink=p2;//因为是无向图，所以有两次建立边表的过程}}//--------------------------------深度优先遍历voidDFS(Graph*G,inti,intvisit[]){coutG-adjlists[i].vertex;visit[i]=1;edgenode*p=newedgenode;p=G-adjlists[i].edgelink;if(G-adjlists[i].edgelink&&!visit[p-endver]){DFS(G,p-endver,visit);}}voidDFStraversal(Graph*G,charc)//深度优先遍历{cout该图的深度优先遍历结果为:endl;intvisit[MaxVerNum];for(inti=0;iG-vexnum;i++){visit[i]=0;//全部初始化为0，即未访问状态}intm;for(inti=0;iG-vexnum;i++){if(G-adjlists[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);break;}}//继续访问未被访问的结点for(inti=0;iG-vexnum;i++){if(visit[i]==0)DFS(G,i,visit);}coutendl;}//------------------------广度优先遍历voidBFS(Graph*G,intv,intvisit[]){QueueList*Q=newQueueList;Q-front=Q-rear=NULL;EnQueue(Q,v);while(Q-rear!=NULL){inte=0;DeQueue(Q,&e);coutG-adjlists[e].vertex;visit[e]=1;edgenode*p=newedgenode;p=G-adjlists[e].edgelink;if(p){intm=p-endver;if(m==0){EnQueue(Q,m);while(visit[m]==0){p=p-edgenext;if(p==NULL)break;m=p-endver;EnQueue(Q,m);}}}}}voidBFStraversal(Graph*G,charc){cout该图的广度优先遍历结果为:endl;intvisited[MaxVerNum];for(inti=0;iG-vexnum;i++){visited[i]=0;}intm;for(inti=0;iG-vexnum;i++){if(G-adjlists[i].vertex==c){m=i;BFS(G,i,visited);break;}}//继续访问未被访问的结点for(inti=0;iG-vexnum;i++){if(visited[i]==0)BFS(G,i,visited);}coutendl;}intmain(){Graph*G=newGraph;CreatAdjList(G);charch;cout请输入开始遍历的顶点:;cinch;DFStraversal(G,ch);BFStraversal(G,ch);return0;}