首页 > 代码库 > 最小生成树

最小生成树

最小生成树n个顶点网络的生成树有n个结点,n-1条分枝。假设网络中有m条边(mn-1),用MST表示许多可能的生成树的集合,每棵树中n-1条分枝上的权之和用WG(T)表示,则使得WG(Tmin)=Min{WG(T)| T     MST}的生成树Tmin便是网络的最小生成树。
 
构造最小生成树的算法Prime算法Kruskal算法
 
      Prime算法
1.可取图中任意一个顶点v 作为生成树的根,之后如果要往生成树上添加顶点w ,则在顶点 v w之间必定存在一条边 (v,w),并且该边的权值在所有连通顶点v w 之间的边中取值最小。
2.一般情况下,假设n个顶点分成两个集合:U(包含已经落在生成树上的顶点)和 V-U(尚未落在生成树上的顶点),则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
 
算法思想假设N=(V{E})是一个连通图,TEN上最小生成树中边的集合。算法从U={u0 }(u0     V)TE={ }开始,重复执行下述操作:在所有u  Uv   VU的边(u, v)    {E}中找一条代价最小的边(u0, v0)并入集合TE,同时v0并入U,直至U=V为止。此时,TE中必有n-1条边,则T=(V{TE})N的最小生成树。
 
如下图所示:

技术分享技术分享

最小生成树