最小生成树程序算法

《最小生成树程序算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、三、!1!五、六、七、摘要概述Prim算法程序运行结果结论参考文献程序代码目录一、摘要1、最小牛成树得定义：在一个具有儿个顶点的连通图G中，如果存在子图G，包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。2、本文用Prim算法实现了生成最小生成树。3、经过试验测试可以求出此图的最小牛成树为：ECD二、概述离散数学(Discretemathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用。随着信息

2、时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位己经发牛了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。图论是离散数学的一个分支。图论起源很早，远在18世纪就出现图论问题,如箸名的哥尼斯堡桥问题就是著名的图论问题。图论使用图的方法研究客观世界的一门科学。在图论中用“结点”表示事物，用“边”表示事物间的联系，而由结点与边所构成的图

3、表示所研究的客观对象。根据图得出生成树有着重要的意义。例如生活中城市间电线的最优线布置，其至在战争屮机器蛇的通信网络设置等等都需要从生成树屮选出一个代价最小得生成树，即最小生成树。赋权无向图的最小牛成树问题作为一个典型的图论问题，迄今为止国内外学者已经对其进行了深入的研究。生成最小生成树主要的方法有避圈法。常见的避圈法有1957年Kruskal提出的Kruskal算法、1957年Prim提出的Prim算法、1959年Dijkstra提出的最小生成树算法。在国内，1975年管梅谷教授提出了破圈算法，其基木思想是在给定的图中任意找出一个回

4、路，删去该回路中权最大的边，然后在余下的图中再任意找出一个回路，再删去这个新找岀的回路中权最大的边，一直重复上述过程，直到剩余的图屮没有回路。此时没有回路的剩余图便是需要求解的最小生成树。2006年孙凌宇和薛锦云教授采用PAR方法通过功能归约变换，形式化推导出递推的最小牛成树算法，简化了算法程序设计和正确性证明的过程。2008年张充等人将最小生成树算法用于对预分类文本的聚类处理，较好地解决了中文版面横竖混排的问题。对于赋权有向图最小生成树问题，仅有较少的研究。1997年吴文虎通过树形图中有向圈的收缩和展开，求解赋权有向图的最小生成树。

5、1998年冯俊文基于赋权有向图的表格表示，给出了一种求解最小生成树的表上作业法。三、Prim算法假设G(V,E)是有n个顶点的连通网络，用T二(U,TE)表示要构造的最小生成树，其中U为顶点集合，TE为边的集合。Prim算法的具体步骤描述如下:(1)初始化：令U={0},TE={0}o从V中取出一个顶点u0放入生成树的顶点集U中，作为第一个顶点，此时T二({u0},{0})；(2)从uU,vV-E的边(u,v)中找一条代价最小的边(屮，v*),将其放入TE屮，并将v*放入U屮。(3)重复步骤(2),直至U二V为止。此吋集合TE中必有n

6、・l条边，T即为所要构造的最小牛成树。上述过程的具体细节如算法见代码所示。四、程序运行结果执行结果:u0ulu2u3u4u5U01000169100011U1110003100010002u26310004101000u3910004100057u41000100010100010008u51121000781000TheMinimal-Span-Treeiscomposedoffollowingedges:edgeWeight<0.1>1<1.5>2<1.2>3<2一3>4<3,4>5Pressanykeytocontinue五、结

7、论1、该程序成功解决了“最小树生成问题”，完成了题目要求。2、根据算法分析岀Prim算法的复杂度与网的边数无关，适合边稠密网络的最小牛成树，但时间复杂度大，程序运行较慢。3、Kruskal算法仅与网中边数有关，适合于边稀疏网络的最小生成树，在时间复杂度方而小于Prim算法，提高程序运行速度。六、参考文献《软件技术基础》西安电子科技大学岀版社周大伟、钟桦等编著2、《离散数学导论》高等教育出版社徐洁磐编著3、百度百科一一“离散数学”图论”，“最小生成树”七.程序代码1、Prim算法:typedefstruct(〃边的存储结构intfrom

8、vex,endvex;〃边的起点和终点intlength;}edge;〃边的权值edgeT[n-l

9、;floatdist[n][n];〃最小生成树〃连通网络的带权邻接矩阵voidPrim(inti)点下标{//i表示最小