最小生成树问题-数据结构课程设计

实习5、最小生成树问题一、需求分析1.问题描述若要在n个城市间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。2.基本要求(1)利用克鲁斯卡尔算法求网的最小生成树。(2)实现教科书6.5节中定义的抽象数据类型MFSet。以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中各边以及它们的权值。3.测试数据4.实现提示通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机函数产生。图的存储结构的选取应和所做操作相适应。为了便于选择权值最小的边，此题的存储结构既不用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。二、概要设计ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={v,w|v,w∈V且P(v,w),v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息}基本操作：CreateUDN(*G)操作结果：创建无向图。MiniSpanTree(G,minedge)（使用克里斯卡尔算法始终调试不成功只好改用普利姆算法）初始条件：图G存在。操作结果：求图G的最小生成树。PrintMinEdge(G,minedge)初始条件：图G存在。操作结果：输出图G的最小生成树。}ADTGraph三、详细设计（源代码）（使用C语言时指针参数传递总是出问题只好改用C++语言）#includestdio.h#includestdlib.h#defineMAX10//本程序设最大顶点数为10typedefstruct{intvexnum;//点数量intarcnum;//边数量intarcs[MAX][MAX];//边存储charvexs[MAX];//点存储}iGraph;typedefstructclose{intadjvex;intendvex;intlowcost;//最小权值}*closedge,closedges;voidCreateUDN(iGraph*G){//创建无向图inti,j,m,k,l,cost;charname1,name2;printf(请输入顶点数和边数（注意：边数大于或等于顶点数）：\n);scanf(%d%d,&G-vexnum,&G-arcnum);getchar();printf(请输入各个顶点名字：\n);for(i=0;iG-vexnum;i++){scanf(%c,&G-vexs[i]);getchar();}for(i=0;iG-vexnum;i++)for(j=0;jG-vexnum;j++)G-arcs[i][j]=100;//初始化边的权值此程序设100为最大值for(i=0;iG-arcnum;i++){printf(请输入第%d条边（输入格式为：端点1-端点2:权值）：\n,i+1);scanf(%c-%c:%d,&name1,&name2,&cost);getchar();for(j=0;jG-vexnum;j++)//在表中查找点{if(name1==G-vexs[j])k=j;}for(m=0;mG-vexnum;m++)//在表中查找点{if(name2==G-vexs[m])l=m;}if(k==l)//两个点如果相同，报错{i--;printf(输入错误的数据,请重新输入\n);continue;}G-arcs[k][l]=cost;//无向边赋权值G-arcs[l][k]=cost;}//使输入的边赋值for(i=0;iG-vexnum;i++)for(j=0;jG-vexnum;j++)if(i==j)G-arcs[i][j]=0;//如果端点相同，则不存在边}voidMiniSpanTree(iGraphG,closedge&minedge){//求最小生成树inti,j,k,z;inttemp;intcurrentmin;k=0;minedge=(closedge)malloc((G.vexnum+1)*sizeof(closedges));for(j=1;jG.vexnum;j++){minedge[j-1].adjvex=k;minedge[j-1].endvex=j;minedge[j-1].lowcost=G.arcs[k][j];}for(i=0;iG.vexnum-1;i++){currentmin=minedge[i].lowcost;k=i;for(j=i+1;jG.vexnum-1;j++){if(minedge[j].lowcostcurrentmin){currentmin=minedge[j].lowcost;k=j;}}//交换第k个元素和第i个元素temp=minedge[i].adjvex;minedge[i].adjvex=minedge[k].adjvex;minedge[k].adjvex=temp;temp=minedge[i].endvex;minedge[i].endvex=minedge[k].endvex;minedge[k].endvex=temp;temp=minedge[i].lowcost;minedge[i].lowcost=minedge[k].lowcost;minedge[k].lowcost=temp;for(j=i+1;jG.vexnum-1;j++){z=minedge[i].endvex;//Z为新找到的顶点k=minedge[j].endvex;if(k!=z){if(G.arcs[z][k]minedge[j].lowcost){minedge[j].adjvex=z;minedge[j].lowcost=G.arcs[z][k];//和以前的节点比较，如果边的权值小，则选取已有的结点中权值最小的边}}}}}voidPrintMinEdge(iGraphG,closedgeminedge)//输出所求最小生成树{inti,sum;sum=0;printf(最小生成树对应的边为\n);for(i=0;iG.vexnum-1;i++){printf(%c-%c:权值为：%d\n,G.vexs[minedge[i].adjvex],G.vexs[minedge[i].endvex],minedge[i].lowcost);sum=sum+minedge[i].lowcost;}printf(最小生成树的权值为：%d,sum);}intmain(){//主函数printf(*******************************************************\n);printf(**\n);printf(*最小生成树问题*\n);printf(**\n);printf(*******************************************************\n);iGraphG;closedgeminedge;CreateUDN(&G);//输入无向网printf(\n);MiniSpanTree(G,minedge);//求最小生成树PrintMinEdge(G,minedge);//输出最小生成树printf(\n);return0;}四、调试分析编译环境为CodeBlocks。