文档介绍：最小生成树算法最小生成树:在一给定的无向图G=(V,E)中,(u,v)代表连接顶点u与顶点v的边,而w(u,v)代表此边的权重,若存在T为E的子集且为无循环图,使得•⑴二w(T)最小,则此T为G的最小生成树。Ya){urv)(ufv)et最小牛:成树其实是最小权重4:成树的简称o最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个非空真子集。若(u,v)是G中一条一个端点在U中(例如:uEU),另一个端点不在U中的边(例如:vGV-U),•且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)o一个有n个结点的连通图的生成树是原图的极小连通了图,且包含原图中的所有n个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。一•性质:最小生成树性质:设G二(V,E)是一个连通网络,U是顶点集V的一个非空真子集。若(u,v)是G中一条〃一个端点在U中(例如:ueu),另一个端点不在U中的边(例如:vEV-U),且(u,V)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)o起源和发展:计算稠密图的最小生成树最早是市罗伯特•普里姆在1957年发明的,即Prim算法。之后艾兹赫尔•戴克斯特拉也独口发明了它。但该算法的基本思想是由沃伊捷赫•亚尔尼克于1930年发明的。所以该算法有时候也被称为Jarnik算法或者Prim-Jarnik算法。20世纪70年代,优先队列发明之后很快被用在了寻找稀疏图中的最小生成树上。1984年,迈克尔•弗里德曼和罗伯特•塔扬发明了斐波那契堆,Prim算法所需要的运行时间在理论上由ElogE提升到了E+VlogVo约瑟夫•克鲁斯卡尔在1956年发表了他的算法,在他的论文中提到了Prim算法的一个变种,而奥塔卡尔•布卢瓦卡在20世纪20年代的论文中就已经提到了该变种。,该算法后成为实现较好渐进性能的最小生成树算法和并行最小生成树算法的基础。应用:生成树和最小生成树有许多重要的应用。例如:要在n个城市之间铺设光缆,主要目标是耍使这n个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。算法描述:求MST的一般算法可描述为:针对图G,从空树T开始,往集合T中逐条选择并加入n・l条安全边(u,v),最终生成一棵含nJ条边的MSTo当一条边(u,v)加入T时,必须保证TU{(u,v)}仍是MST的子集,我们将这样的边称为T的安全边。1•最小生成树Prim算法简述・输入:一个加权连通图,其中顶点集合为V,边集合为E;•初始化:Vnew={x},其中x为集合V中的任一节点(起始点),Enew={},为空;•重复卜'列操作,直到Vnew=V:a・在集合E中选取权值最小的边<u,v>,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并Kvev(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);b・将v加入集合Vnew中,将vu,v>边加入集合Enew中;.输出:使用集合Vnew和Enew来描述所得到的最小生成树。[1]