数据结构实验六-图结构及其应用

实验七图结构及其应用一、实验目的1.掌握图类的邻接矩阵存储结构的实现；2.掌握图的基本操作，包括图的建立、广度优先遍历和深度优先遍历算法；3.掌握求最短路径的Dijkastra算法。二、实验要求1.复习课本中第7章关于图的相关知识内容；2.用C++语言完成算法和程序设计并且调试通过；三、实验题目与要求1．图的遍历详细描述：利用以提供的源程序素材，实现对不多于30个结点的图的建立以及广度优先和深度优先遍历算法。具体功能要求：从键盘中输入网中顶点的个数，以及顶点的数据值，并以顶点的输入次序作为顶点的编号输入顶点与顶点之间的邻接边的权值（注：若为无向图，则每条边可由两条方向相反的有向边构成）；若无边相连则已设定的权值最大值MaxWeight=1000代替。利用顶点与边的信息建立网的邻接矩阵，并第一个输入的顶点为原点对网进行深度优先和广度优先遍历，并输入遍历的顶点序列。例：如下图7-1图所示，则输入为：6ABCDEF18AB34AE12BA34BC46BF19CB46CD17CF25DC17DE38DF25EA12ED38EF26FB19FD25FC25FE262512341926463825ABCDEF17图7-1网的图示表示在提供的程序模板中，完成以下函数，实现上述功能；(1)DFSTraverse(MGraphG)功能描述：对网进行深度优先遍历，网可以非连通(2)BFSTraverse(MGraphG)功能描述：对网进行广度优先遍历，网可以非连通2．最短路径求解详细描述:在第一题的基础上，Dijkastra算法求解从第A个顶点到其余各个顶点的最短路径的所经过的顶点以及路径的长度。例：如图7-1所示，则该求出顶点A到其余个顶点的最短路径所经过的顶点，以及路径的长度；输出如下所示：A-B:AB34A-C:AEFC63A-D:AED50A-E:AE12A-F:AEF38在提供的程序模板中，完成以下函数，实现上述功能；voiddijkstra(MGraphG,intvs)3.验证练习先对下图7-2和7-3进行深度和广度优先遍历，并求出以A作为源点求最短路径的结果。并通过输入图的信息执行图的遍历和求最短路径程序，比较运行结果与你求的结果是否一致，若有不一致请查明原因。10ABCDEF7202218208015405181610ABCDEF720182511309530图7-2图7-3四、程序代码及运行结果【程序代码】#includestdio.h#includestdlib.h//#includestdbool.h#includelimits.h#defineboolint#definetrue1#definefalse0#defineMAX_VERTEX_NUM20//最大顶点个数#defineINFINITYINT_MAX//最大值∞typedefcharVertexType;//顶点向量类型typedefintVRType;typedefintInfoType;typedefintQElemType;//图的数组存储表示typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量VRTypearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];;//邻接矩阵,于无权图1、0表示两个顶点是否相邻，对于有权图为权值intvexnum,arcnum;//图的顶点数和弧数}MGraph;boolvisited[MAX_VERTEX_NUM];//标记顶点是否被访问，访问为true,否则为false//查找顶点在顶点向量中的位置intlocateVertex(MGraphumg,VertexTypev){inti;for(i=0;iumg.vexnum;i++){if(v==umg.vexs[i])returni;}return-1;}//创建无向（有向）无权图voidcreateUMGraph(MGraph*umg){inti,j,v;charv1,v2;printf(输入无权图的顶点数和边数\n);scanf(%d%d,&(*umg).vexnum,&(*umg).arcnum);for(v=0;v(*umg).vexnum;v++)visited[v]=false;getchar();printf(输入顶点名称\n);for(v=0;v(*umg).vexnum;v++){printf(输入第%d个顶点名称：,v);scanf(%c,&(*umg).vexs[v]);getchar();}//初始化邻接矩阵for(i=0;i(*umg).vexnum;i++)for(j=0;j(*umg).vexnum;j++)(*umg).arcs[i][j]=0;//将图中相邻的顶点的邻接矩阵值设为1，不相邻仍为0printf(输入边的信息，输入边的两个顶点名称v1v2\n);for(v=0;v(*umg).arcnum;v++){printf(输入第%d条边两个顶点:,v);scanf(%c%c,&v1,&v2);getchar();printf(\n);i=locateVertex(*umg,v1);j=locateVertex(*umg,v2);//(*umg).arcs[i][j]=(*umg).arcs[j][i]=1;//由于是无向图，因此一条边关联两个顶点(*umg).arcs[i][j]=1;//有向图，边为单向}}//创建无向（有向）有权图voidcreateMGraph(MGraph*mg){inti,j,v,w;charv1,v2;printf(输入有权图的顶点数和边数\n);scanf(%d%d,&(*mg).vexnum,&(*mg).arcnum);for(v=0;v(*mg).vexnum;v++)visited[v]=false;getchar();printf(输入顶点名称\n);for(v=0;v(*mg).vexnum;v++){printf(输入第%d个顶点名称：,v);scanf(%c,&(*mg).vexs[v]);getchar();}//初始化邻接矩阵for(i=0;i(*mg).vexnum;i++)for(j=0;j(*mg).vexnum;j++)(*mg).arcs[i][j]=INFINITY;//将图中相邻的顶点的邻接矩阵值设为边的权值printf(输入边的信息，输入边的两个顶点名称和权值v1v2w\n);for(v=0;v(*mg).arcnum;v++){printf(输入第%d条边两个顶点和权值:,v);scanf(%c%c%d,&v1,&v2,&w);getchar();i=locateVertex(*mg,v1);j=locateVertex(*mg,v2);//(*mg).arcs[i][j]=(*mg).arcs[j][i]=w;//由于是无向图，因此一条边关联两个顶点(*mg).arcs[i][j]=w;//有向图，边为单向}}//打印图的邻接矩阵voidprint(MGraphG){inti,j;printf(图的邻接矩阵\n);for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++){if(G.arcs[i][j]!=INFINITY)printf(%d,G.arcs[i][j]);elseprintf(∞);}printf(\n);}printf(\n);}//深度优先遍历图intFirstAdjVex(MGraphG,intv){//获取与顶点v相邻的第一个顶点下标inti;for(i=0;iG.vexnum;i++){if(G.arcs[v][i]!=0&&G.arcs[v][i]!=INFINITY&&!visited[i])returni;}return-1;}intNextAdjVex(MGraphG,intv,intw){//得到v的下一个未被访问的相邻顶点下标inti;for(i=w;iG.vexnum;i++){if(G.arcs[v][i]!=0&&G.arcs[v][i]!=INFINITY&&!visited[i])returni;}return-1;}voidDFS(MGraphG,intv){intw;visited[v]=true;printf(%c,G.vexs[v]);//访问第v个顶点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS}voidDFSTraverse(MGraphG){printf(深度优先遍历序列：);intv;for(v=0;vG.vexnum;v++)visited[v]=false;for(v=0;vG.vexnum;v++)if(!visited[v])DFS(G,v);printf(\n);}//广度优先遍历//创建用于广度优先遍历的队列typedefstructQNode{QElemTypedata;structQNode*qnext;}QNode,*PQNode;typedefstructQueue{PQNodefront;PQNoderear;}Queue,*PQueue;//初始化一个空队列PQueueinitQueue(){PQueuepqueue=(PQueue)malloc(sizeof(Queue));PQNodepqnode=(PQNode)malloc(sizeof(QNode));if(pqnode==NULL){printf(队列头空间申请失败！\n);exit(-1);}pqueue-front=pqueue-rear=pqnode;pqnode-qnext=NULL;returnpqueue;}//队尾入队voidenQueue(PQueuepqueue,QElemTypedata){PQNodepqnode=(PQNode)malloc(sizeof(QNode));if(pqnode==NULL){printf(队列结点申请失败！\n);exit(-1);}pqnode-data=data;pqnode-qnext=NULL;pqueue-rear-qnext=pqnode;pqueue-rear=pqnode;}//判断队列是否为空boolisEmpty(PQueuepqueue){if(pqueue-front==pqueue-rear)returntrue;returnfalse;}//队头出队QElemTypedeQueue(PQueuepqueue){if(isEmpty(pqueue)){printf(队列为空\n);exit(-1);}PQNodepqnode=pqueue-front-qnext;pqueue-front-qnext=pqnode-qnext;if(pqnode==pqueue-rear)pqueue-rear=pqueue-front;QElemTypedata=pqnode-data;free(pqnode);returndata;}voidBFSTraverse(MGraphG){printf(广度优先遍历序列：);inti,v,w;for(i=0;iG.vexnum;i++)visited[i]=false;PQueuepqueue=initQueue();//初始化辅助队列for(i=0;iG.vexnum;i++){if(!visited[i])//i未被访问{visited[i]=true;printf(%c,G.vexs[i]);enQueue(pqueue,i);while(!isEmpty(pqueue)){v=deQueue(pqueue);//队头元素出队for(w=Fir