资源描述：
《【信息与计算科学专业】【毕业论文】最小生成树算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、本科毕业论文（20届）最小生成树算法及其应用16摘要最小生成树是图论中的一个既经典又重要的问题.它体现在图这种数据结构上的应用涉及到我们的日常,工程,学术以及科研等方方面面.最小生成树广泛的应用价值主要取决于其通俗简单的理论算法和严密成熟的数学基础.本文首先介绍最小生成树的相关理论;其次给出几种最小生成树的经典算法,在此基础上对这些算法的优缺点进行分析比较,得到一些相关结论;最后介绍最小生成树经典算法以及最小生成树在各领域中的几种代表算法的应用.关键词:最小生成树;Prim算法;Kruskal算法;应用16AbstractMinimumspanningt
2、reeisbothaclassicandimportantissuesingraphtheory.Theapplicationsofminimumspanningtreereflectingonthedatastructurerelatedtoserialaspectsofourdailylife,engineering,academicandscientificresearch.It’swidelyapplicationsdependonsimpletheoryandstrictmaturemathematicalbasis.Firstly,thist
3、hesisintroducessomebasictheoriesaboutminimumspanningtree;Secondly,itgetssomekindsofclassicalgorithms,onthisbasis,itanalyzesandcomparestheadvantagesanddisadvantagesofthesealgorithms,thenachievessomeconclusion;Lastly,itintroduceapplicationsofbothclassicalgorithmsandthoserepresentat
4、ivealgorithmsinmanyareas.Keywords:Minimumspanningtree;Primalgorithm;Kruskalalgorithm;Applications16目录摘要IABSTRACTII1前言12最小生成树的定义及性质32.1最小生成树定义32.2最小生成树的性质43最小生成树的两种经典算法63.1Prim算法63.2kruskal算法63.3算法分析与比较74经典算法及改进算法的应用84.1Prim算法应用84.2kruskal算法应用84.3其它算法与应用125小结14参考文献15致谢17161前言树是图论的
5、重要内容,在计算机科学技术,特别是数据结构中有广泛的应用.关于赋权图的应用,常常需要我们求解一棵无向生成树,使其边的总权值最小.这样的一棵生成树称作最小生成树(minimumspanningtree,MST).最小生成树算法也是重要的计算方法,是现代科学中比较热门的研究方向.许多应用问题都是一个求无向连通图的最小生成树问题.例如:要在个城市之间铺设光缆,主要目标是要使这个城市的任意两个之间都可以通信,但铺设光缆的费用很高,而且各个城市之间铺设光缆的费用不同;另一个目标是要使铺设光缆的总费用最低.这就需要找到带权的最小生成树.许多研究工作表明,最小生成树结
6、构是通信网络设计的最优拓扑结构.然而,实际的网络优化问题通常需要满足附加的约束.因此形成了带约束的最小生成树问题,例如:（1）概率最小生成树问题;（2）叶子约束最小生成树问题;（3）随机最小生成树问题;（4）容量限制的最小生成树问题等.最小生成树算法从1920年就已经出现.然而,研究人员仍在寻求更好的方法.因为这个问题并没有得到完全的理解.经典的MST算法其实现的效率大相径庭,这些算法（例如Boruvka,Prim算法等）在做运算时大都要求一次将数据读入内存中以做比较,如果处理的是大型图,内存无法一次就把所有的数据读入,这些算法将受到一定局限性（虽然也有
7、一些片外排序的技术,但其实现也不容易）.针对这个问题,罗竣友,尤众,赵军辉等提出了一种新的算法以实现在无向连通图中寻找最小生成树,该算法基于分治法的思想,将主要的排序分为两部分,在每部分中的子运算只要求读入内存很少的数据以做比较.陶午沙,沈振康,李吉成提出一种融合多元模糊空间关系信息的支撑树搜索算法,即S2Prim(spatialPrim)算法,用以识别低分辨率环境下(红外、多光谱遥感、SAR、恒星导航等图像中)具有规则空间分布关系的目标斑点集合.徐磊,张兢引入了节点的度的定义,据此提出了广义最小生成树的概念.采用遗传算法来求解最小生成树,井针对普通遗传
8、算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略,通
