最小生成树问题

榆林学院12届课程设计《最小生成树问题》课程设计说明书学生姓名：赵佳学号：12院系：信息工程学院专业：计算机科学与技术班级：计14本1指导教师：答辩时间：年月日最小生成树问题一、问题陈述最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。二、需求分析1.在n个城市之间建设网络，只需保证连通即可。2.求城市之间最经济的架设方法。3.采用多种存储结构，求解算法也采用多种。三、概要设计1、功能模块图2、功能描述（1)CreateUDG()创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。（2)Switch()功能选择：给用户提示信息，让用户选择相应功能。（3)Adjacency_Matrix()建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。（4)Adjacency_List()开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表算法4.PRIM算法结束建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。（5)MiniSpanTree_KRSL()kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。（6)MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。四、详细设计本次课程设计采用两种存储结构以及两种求解算法。1、两种存储结构的存储定义如下：typedefstructArcell{doubleadj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];dj=MAX;}开始标志顶点1加入U集合寻找满足边的一个顶点在U,另一个顶点在V的最小边形成n-1条边的生成树顶点k加入U修改由顶点k到其他顶点边的权值结束得到最小生成树CreateUDG()main()Adjacency_Matrix()Adjacency_List()MiniSpanTree_KRSL()MiniSpanTree_PRIM()locateVex()locateVex()Minimum()locateVex()Sortdge()cout请输入两个城市名称及其连接费用(严禁连接重复输入!)：endl;for(k=0;k;++k){cindgevalue[k].ch1dgevalue[k].ch2dgevalue[k].value;i=LocateVex(G,dgevalue[k].ch1);j=LocateVex(G,dgevalue[k].ch2);[i][j].adj=dgevalue[k].value;[j][i].adj=[i][j].adj;}returnOK;}intLocateVex(MGraphG,charch)dj==MAX)cout0;elsecout[i][j].adj;coutendl;}}voidAdjacency_List(MGraphG,Dgevaluedgevalue)h1==[i]&&dgevalue[j].ch2!=[i])coutdgevalue[j].ch2-;elseif(dgevalue[j].ch1!=[i]&&dgevalue[j].ch2==[i])coutdgevalue[j].ch1-;cout\b\bendl;}}voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)h1)];p2=bj[LocateVex(G,dgevalue[i].ch2)];if(p1!=p2){cout城市dgevalue[i].ch1与城市dgevalue[i].ch2连接。endl;for(j=0;j;j++){if(bj[j]==p2)bj[j]=p1;}}}}voidSortdge(Dgevalue&dgevalue,MGraphG)aluedgevalue[j].value){temp=dgevalue[i].value;dgevalue[i].value=dgevalue[j].value;dgevalue[j].value=temp;ch1=dgevalue[i].ch1;dgevalue[i].ch1=dgevalue[j].ch1;dgevalue[j].ch1=ch1;ch2=dgevalue[i].ch2;dgevalue[i].ch2=dgevalue[j].ch2;dgevalue[j].ch2=ch2;}}}}voidMiniSpanTree_PRIM(MGraphG,charu)djvex=u;closedge[j].lowcost=[k][j].adj;}}closedge[k].lowcost=0;for(i=1;i;i++){k=Minimum(G,closedge);cout城市closedge[k].adjvex与城市[k]连接。endl;closedge[k].lowcost=0;for(j=0;j;++j){if[k][j].adjclosedge[j].lowcost){closedge[j].adjvex=[k];closedge[j].lowcost=[k][j].adj;}}}}intMinimum(MGraphG,Closedgeclosedge)owcost!=0&&closedge[i].lowcostk){k=closedge[i].lowcost;j=i;}}returnj;}voidmain(){MGraphG;Dgevaluedgevalue;CreateUDG(G,dgevalue);charu;cout图创建成功。;cout请根据如下菜单选择操作。\n;cout1、用邻接矩阵存储：endl;cout2、用邻接表存储：endl;cout3、克鲁斯卡尔算法求最经济的连接方案endl;cout4、普里姆算法求最经济的连接方案endl;ints;chary='y';while(y='y'){cout请选择菜单：endl;cins;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;cout请输入起始城市名称：;cinu;MiniSpanTree_PRIM(G,u);break;default:cout输入有误!;break;}coutendl是否继续？y/n:;ciny;if(y=='n')break;}}五、运行结果与测试六、设计体会与总结通过本次课程设计，我在程序设计中，用邻接矩阵和邻接表这两种存储结构进行编程，且对Prim算法和Kruskal算法生成最小生成树有了一个初步的了解，同时也为日后的毕业设计打下了良好的基础。而且通过课程设计在下述各方面得到了锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。在本次课程设计中，知道如何在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。并且用了多种求解方式。这几天的课程设计让我充分地体会到了上机实践对于计算机编程的重要性。只顾学习理论是远远不够的。实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。