最小生成树-文献综述.doc

毕业设计(论文)文献综述题目:最小生成树算法及其应用学院:数理与信息学院学生姓名:许立学号:0专业:信息与计算科学班级:A07信息指导老师:陈丽燕起止日期:-(minimumspanningtree,MST)是计算机学科中一重要内容,其算法也是重要的计算方法,,且包含原图中的所有n个结点,:要在n个城市之间铺设光缆,主要目标是要使这n个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同;:最小生成树性质:设G=(V,E)是一个连通网络,(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)[1].求MST的一般算法可描述为:针对图G,从空树T开始,往集合T中逐条选择并加入n-1条安全边(u,v),最终生成一棵含n-(u,v)加入T时,必须保证T∪{(u,v)}仍是MST的子集,::该算法由Prim提出,=(V,E),其生成树的顶点集合为U.①、把v0放入U.②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树.③、把②,则结束,(n^2).Prim算法实现:(1)集合:设置一个数组set(i=0,1,..,n-1),初始值为0,代表对应顶点不在集合中(注意:顶点号与下标号差1)(2)图用邻接矩阵或邻接表表示,路径不通用无穷大表示,在计算机中可用一个大整数(如1<<30)(mlogn),如果采用Fibonaci堆可以将复杂度降为O(nlogn+m)Kruskal算法:每次选择n-1条边,所使用的贪婪准则是:,,,若将其加入到已选边的集合中会出现环路,则将其抛弃,否则,将它选入[2].假设WN=(V,{E})是一个含有n个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,,从网的边集E中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,