最小生成树问题

1、 最小生成树问题（总10页）-本页仅作为文档封面，使用时请直接删除即可-内页可以根据需求调整合适字体及大小-最小生成树问题课程设计说明书学生姓名：赵佳学号：丄院系：信息工程学院专业：计算机科学与技术班级：计14本1指导教师：答辩时间：年月日最小生成树问题一、问题陈述最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。二、需求分析在n个城市之间建设网络，只需保证连通即可。求城市之间最经济的架设方法。采用多种存储结构，求解算法也采用多种。三、概要设计1、功能模块图2、功能描述CreateUDG()创建一个图：通过给用户信息提示，让用

2、户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。Switch()功能选择：给用户提示信息，让用户选择相应功能。Adjacency_Matrix()建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。Adjacency_List()建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。MiniSpanTree_KRSL()kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。四、详细设计本次课程设计

3、采用两种存储结构以及两种求解算法1、两种存储结构的存储定义如下：typedefstructArcelldoubleadj;Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructcharvexsMAX_VERTEX_NUM;开始标志顶点1加入u集合形成n-1条边的生成树寻找满足边的一个顶点在U,另一个顶点在V的最小边*结束 dj=MAX;cout请输入两个城市名称及其连接费用(严禁连接重复输入!):endl;for(k=0;kdgevaluek.ch1dgevaluek.ch2dgevaluek.value;i=LocateVex(G

4、,dgevaluek.ch1);j=LocateVex(G,dgevaluek.ch2);j.adj=dgevaluek.value;ji.adj=ij.adj;returnOK;intLocateVex(MGraphG,charch)dj=MAX)cout0;elsecoutij.adj;coutendl;voidAdjacency_List(MGraphG,Dgevaluedgevalue)h1=i&dgevaluej.ch2!=i)coutdgevaluej.ch2;elseif(dgevaluej.ch1!=i&dgevaluej.ch2=i)coutdgevaluej.ch1;cou

5、tbbendl;voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)h1);p2=bjLocateVex(G,dgevaluei.ch2);if(p1!=p2)cout城市dgevaluei.ch1与城市dgevaluei.ch2连接。”endl;for(j=0;jdgevaluej.value)temp=dgevaluei.value;dgevaluei.value=dgevaluej.value;dgevaluej.value=temp;ch1=dgevaluei.ch1;dgevaluei.ch1=dgevaluej.ch1;dgevaluej

6、.ch1=ch1;ch2=dgevaluei.ch2;dgevaluei.ch2=dgevaluej.ch2;dgevaluej.ch2=ch2;voidMiniSpanTree_PRIM(MGraphG,charu)djvex=u;closedgej.lowcost=kj.adj;closedgek.lowcost=0;for(i=1;i;i+)k=Minimum(G,closedge);cout城市closedgek.adjvex与城市k连接。endl;closedgek.lowcost=0;for(j=0;j;+j)ifkj.adjclosedgej.lowcost)closedgej.

7、adjvex=k;closedgej.lowcost=kj.adj;intMinimum(MGraphG,Closedgeclosedge)owcost!=0&closedgei.lowcostk)k=closedgei.lowcost;j=i;returnj;voidmain()MGraphG;Dgevaluedgevalue;CreateUDG(G,dgevalue);charu;cout图创建成功。”；cout请根据如下菜单选择操作n;cout1、用邻接矩阵存储：endl;cout2、用邻接表存储：endl;cout3、克鲁斯卡尔算法求最经济的连接方案endl;cout4、普里姆算法求最

8、经济的连接方案endl;ints;chary=y;while(y=y)cout请选择菜单：s;switch(s)case1:cout用邻接矩阵存储为：endl;Adjacency_Matrix(G);break;case2:cout用邻接表存储为：endl;Adjacency_List(G,dgevalue);break;case3:cout克鲁斯卡尔算法最经济的连接方案为:endl;MiniSpanTree_KRSL(G,dgevalue);break;case4:cout普里姆算法最经济的连接方案为:endl;coutu;MiniSpanTree_PRIM(G,u);break;defau

9、lt:cout输入有误!”；break;coutendly;if(y=n)break;五、运行结果与测试*G:(4Debugzuixioa.exe1匚囱创建成珈请:善1S錚冷闢芳橐经帀帀帀汪如lw算起普请曰否竝续？：123为案、打邻接寿子储两:-2-1-3-2；邻接矩阵存储为:0040二告継尊丫n：nressanykeytocontinue曰备六、设计体会与总结通过本次课程设计，我在程序设计中，用邻接矩阵和邻接表这两种存储结构进行编程，且对Prim算法和Kruskal算法生成最小生成树有了一个初步的了解，同时也为日后的毕业设计打下了良好的基础。而且通过课程设计在下述各方面得到了锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水