实验六：图的遍历与最小生成树

数据结构实验六--图的邻接矩阵存储和最小生成树Page1of8实验六图的邻接矩阵存储和最小生成树一、实验目的1．掌握图的邻接矩阵存储结构（或邻接表）2．掌握图的深度优先遍历和广度优先遍历算法2．掌握图的最小生成树算法（Prim算法）二、实验内容按下图所示无向带权图，实现以下各项功能。图1无向带权图1．用图的邻接矩阵（或者邻接表）的方式存储图1的无向带权图。2．输出该无向带权图的顶点序列以及权值集合（采用邻接矩阵存储）。3．分别采用深度优先和广度优先算法遍历该无向图4．采用Prim算法求该无向带权图的最小生成树。要求：实验后用专用实验纸书写报告。报告中要说明实验题目，内容；分析实验过程，总结实验结果。三、设计指导1）创建一个头文件seqlist.h用来保存顺序表相关函数。#defineMaxSize100typedefcharDataType;数据结构实验六--图的邻接矩阵存储和最小生成树Page2of8typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;//初始化ListInitiate(L)voidListInit(SeqList*L){L-size=0;/*定义初始数据元素个数*/}//求当前数据元素个数ListLength(L)intListLength(SeqListL){returnL.size;}//插入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L-size;ji;j--)L-list[j]=L-list[j-1];/*依次后移*/L-list[i]=x;/*插入x*/L-size++;/*元素个数加1*/return1;}//删除数据元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x){intj;*x=L-list[i];/*保存删除的元素到x中*/for(j=i+1;j=L-size-1;j++)L-list[j-1]=L-list[j];/*依次前移*/L-size--;/*数据元素个数减1*/return1;}//取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i0||iL.size-1){数据结构实验六--图的邻接矩阵存储和最小生成树Page3of8printf(参数i不合法!\n);return0;}else{*x=L.list[i];return1;}}2）创建一个头文件seqcqueue.h用来保存循环队列相关函数。#includestdio.h#defineMaxQueueSize20typedefstruct{DataTypequeue[MaxQueueSize];intrear;intfront;intcount;}SeqCQueue;//初始化QueueInit(Q)voidQueueInit(SeqCQueue*Q){Q-rear=0;Q-front=0;Q-count=0;}//非空否QueueNotEmpty(Q)intQueueNotEmpty(SeqCQueueQ){if(Q.count!=0)return1;elsereturn0;}//入队列QueueAppend(Q,x)intQueueAppend(SeqCQueue*Q,DataTypex){if(Q-count0&&Q-rear==Q-front){printf(队列已满无法插入!\n);return0;}数据结构实验六--图的邻接矩阵存储和最小生成树Page4of8else{Q-queue[Q-rear]=x;Q-rear=(Q-rear+1)%MaxQueueSize;Q-count++;return1;}}//出队列QueueDelete(Q,d)intQueueDelete(SeqCQueue*Q,DataType*d){if(Q-count==0){printf(队列已空无数据元素出队列!\n);return0;}else{*d=Q-queue[Q-front];Q-front=(Q-front+1)%MaxQueueSize;Q-count--;return1;}}//取队头数据元素QueueGet(Q,d)intQueueGet(SeqCQueueQ,DataType*d){if(Q.count==0){printf(队列已空无数据元素可取!\n);return0;}else{*d=Q.queue[Q.front];return1;}}3）主函数中包含的部分函数#includestdio.h#includemalloc.h#includeSeqList.h#includeSeqCQueue.h#defineMaxWeight10000数据结构实验六--图的邻接矩阵存储和最小生成树Page5of8#defineMaxVertices10typedefcharVerT;//图的结构体定义typedefstruct{SeqListVertices;intedge[MaxVertices][MaxVertices];intnumOfEdges;}AdjMGraph;//边信息结构体定义typedefstruct{introw;intcol;intweight;}RowColWeight;//最小生成树结构体typedefstruct{VerTvertex;intweight;}MinSpanTree;intvisited1[10]={0};intvisited2[10]={0};//图的初始化voidGraphInit(AdjMGraph*G,intn){//请大家自己完成！！！}//插入顶点voidInsertVertex(AdjMGraph*G,DataTypevertex){//请大家自己完成！！！}//插入一条边voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight){//请大家自己完成！！！}数据结构实验六--图的邻接矩阵存储和最小生成树Page6of8//删除一条边voidDeleteEdge(AdjMGraph*G,intv1,intv2){//请大家自己完成！！！}//取第一个邻接顶点intGetFirstVex(AdjMGraphG,intv){//请大家自己完成！！！}//取下一个邻接顶点intGetNextVex(AdjMGraphG,intv1,intv2){//请大家自己完成！！！}//创建图函数voidCreateGraph(AdjMGraph*G,DataTypeV[],intn,RowColWeightE[],inte){inti,k;GraphInit(G,n);for(i=0;in;i++)InsertVertex(G,V[i]);for(k=0;ke;k++)InsertEdge(G,E[k].row,E[k].col,E[k].weight);}voidVisit(DataTypeitem){printf(%c,item);}//图的深度优先遍历算法voidDepthFSearch(AdjMGraphG,intv){//请大家自己完成！！！}//图的广度优先遍历算法voidBroadFSearch(AdjMGraphG,intv)数据结构实验六--图的邻接矩阵存储和最小生成树Page7of8{//请大家自己完成！！！}//Prim算法建立带权图的最小生成树voidPrim(AdjMGraphG,MinSpanTreecloseVertex[]){//请大家自己完成！！！}voidmain(){AdjMGraphg1;DataTypea[]={'A','B','C','D','E','F','G'};RowColWeightrcw[]={{0,1,50},{1,0,50},{0,2,60},{2,0,60},{1,3,65},{3,1,65},{1,4,40},{4,1,40},{2,3,52},{3,2,52},{2,6,45},{6,2,45},{3,4,50},{4,3,50},{3,5,30},{5,3,30},{3,6,42},{6,3,42},{4,5,70},{5,4,70}};intn=7,e=20;inti,j;MinSpanTreecloseVertex[7];CreateGraph(&g1,a,n,rcw,e);//DeleteEdge(&g1,0,4);printf(顶点集合为：\n);for(i=0;ig1.Vertices.size;i++)printf(%c,g1.Vertices.list[i]);printf(\n);printf(权值集合为：\n);for(i=0;ig1.Vertices.size;i++){for(j=0;jg1.Vertices.size;j++)printf(%5d,g1.edge[i][j]);printf(\n);}printf(深度优先遍历序列为：\n);DepthFSearch(g1,0);数据结构实验六--图的邻接矩阵存储和最小生成树Page8of8printf(\n广度优先遍历序列为：\n);BroadFSearch(g1,0);printf(\n);Prim(g1,closeVertex);//输出Prim函数得到的最小生成树的顶点序列和权值序列printf(初始顶点=%c\n,closeVertex[0].vertex);for(i=1;in;i++)printf(顶点=%c边的权值=%d\n,closeVertex[i].vertex,closeVertex[i].weight);}4）运行结果如下所示：