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

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