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

《数据结构课程设计-最小生成树问题　》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实习5、最小生成树问题一、需求分析1.问题描述若要在n个城市间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信W，是一个W的最小生成树问题。2.基本要求(1)利用克魯斯卡尔算法求网的最小生成树。(2)实现教科书6.5节中定义的抽象数据类型MFSeto以此表示构造生成树过程中的连通分量。⑶以文本形式输出生成树中各边以及它们的权值。3.测试数据4.实现提示通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利川C语言提供的随机函数产生。阁的存储

2、结构的选取应和所做操作相适应。为了便于选择权伉最小的边，此题的存储结构既不用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组表示图。二、概要设计ADTGraph{数椐对象V:V是具有相同特性的数裾元素的集合，成为顶点集。数据关系R:R={VR}V,wev且P(V,表示从V到W的弧，谓词P(V,w}定义了弧＜^77＞的意义或信息}基本操作：CreateUDN(*G)操作结果：创建无向阁。MiniSpanTree(G，minedge)(使用克里斯卡尔算法始终调试不成功只好改用普利姆算法)初始条件：图G存在。操作结果：求图G的最小生成树。Print

3、MinEdge(G，minedge)初始条件：阁G存在。操作结果：输出图G的最小生成树。}ADTGraph三、详细设计（源代码）（使用C语言吋指针参数传递总是出问题只好改用C++语言）#tdio.h>#inlib.h〉#defineMAX10//本程序设最大顶点数为10typedefstruct{intvexnum;//点数量intarcnum;//边数US:intarcs[MAX][MAX];//边存储charvexs[MAX];//点存储}iGraph;typedefstructclose{intadjvex;intendvex;intlowcost;/

4、/最小权值}*closedge，closedges;voidCreateUDN(iGraph*G){//创建无向图inti，j，m，k，l，cost;charname1，name2;printf(”请输入顶点数和边数(注意：边数大于或等于顶点数)：");scanf("%d%d",m);getchar();printf("请输入各个顶点名字：’’)；fo>vexnum;i++){scanfvexs[i]);getchar();}for(exnum;i++)fo〉vexnum;j++)G->arcs[i][j]=100;//初始化边的权值此程序设100为

5、最大值for(rcnum;i++){printff请输入第％(1条边(输入格式为：端点1-端点2:权值)：",i+l);scanf("%c-%c:%dt);getchar();f->vexnum;j++)//在表屮查找点{if(namel==G->vexs[j])k=j；}G-〉vexnum;m++)//卉:表屮査找点{if(name2==G-〉vexs[mJ)1=m;}if(k==1)//两个点如果相同，报错{i―;printf("输入错误的数据，请重新输入");continue;}G->arcslkj[lj=cost;//无向边赋权值G->arc

6、s[l][k]=cost;}//使输入的边赋值for(ixnum;i++)forvexnum;j++)if(i=j)G-〉arcs[il[jl=O;//如果端点相同，则不存在边}voidMiniSpanTree(iGraphG,closedge{//求最小生成树inti，j，k，z;inttemp;intcurrentmin;k=0;minedge=(closedge)malloc((G.vexnum+1)*sizeof(closedges));for(j=l;jj++){minedge[j-1].adjvex=k;minedge

7、j-1J.endvex=j

8、;minedge[j-1].lowcost=G.arcs[k][j];}G.vexnum-1;i++)currentmin=minedge[i].lowcost;k=i;foG.vexnum-1;j++){if(minedge[j].rrentmin){currentmin=minedgefjl.lowcost;k=j；}}//交换第k个元素和第i个元素temp=minedge[i].adjvex;minedge[i].adjvex=minedge[k].adjvex;minedge[k].adjvex=temp;ternp=minedge[ij.endve

9、x;minedge[i].endvex=minedg