Kruskal算法一一种求最小生成树的算法 设n阶无向连通带权图G=<V,E,W>有m条 边不妨设G中无环否则可先删去),算法为: (1)将m条边按权从小到大顺序排列,设为 1529··m (2)取e1在T中,然后依次检查e2, ·,mr 若e 〔=2,3,…,m与T中的边不能构成回路,则取e在T 中,否则放奔e,考虑下一亲边,直至jm。 (3)算法停止时得到的T为G的最小生成树
设n阶无向连通带权图G=<V,E,W>有m条 边,不妨设G中无环(否则可先删去)，算法为： (1) 将m条边按权从小到大顺序排列，设为 e1 ,e2 , … ,em。 (2) 取e1在T中，然后依次检查e2 , … ,em ，若ej (j=2,3, …,m)与T中的边不能构成回路，则取ej在T 中，否则放弃ej，考虑下一条边，直至j>m。 (3) 算法停止时得到的T为G的最小生成树。 Kruskal算法 — 一种求最小生成树的算法
例:下图(a)出了一个赋权图G,用 kruskal算法求出G 的最小生成树。 解:先将m条边按权由小到大排列: 4 18 r(16 VAst 45 55 2 25 r(13 它们的权分别是:3,4,5,6,6.5,7,7.5,8,10.5,1112,13 逐次取边:(v4,"5V,y),(v"n),(v6,以),(v2,7) 2 构成的生成树在下图(b),这是G的最小生成树。最 小生成树T的权C(T)=3+45+6+75+10.5+11=47。 7.5 7.5 10.5 10.58
例：下图 (a)给出了一个赋权图G，用kruskal算法求出G 的最小生成树。 解：先将m条边按权由小到大排列： (v4 ,v5 )，(v1 ,v8 )，(v5 ,v7 )，(v6 ,v7 )，(v4 ,v6 )，(v5 ,v6 )， (v2 ,v7 )，(v2 ,v5 )，(v7 ,v8 )，(v2 ,v3 )，(v3 ,v4 )，(v1 ,v2 )。 它们的权分别是：3,4,5,6,6.5,7,7.5,8,10.5,11,12,13。 逐次取边：(v4 ,v5 ),(v1 ,v8 ),(v5 ,v7 ),(v6 ,v7 ),(v2 ,v7 ),(v7 ,v8 ),(v2 ,v3 ) 构成的生成树在下图 (b)，这是G的最小生成树。最 小生成树T的权C(T)=3+4+5+6+7.5+10.5+11=47
例:用避圈法求下图所示的最小生成树 解:W(T)=1+2+3+4+5=15,图中黄色为最 小生成树。 5 5 f 5 3 6/4 6
例:用避圈法求下图所示的最小生成树 a b c d e f 5 5 5 5 1 3 6 6 4 2 解: W(T)=1+2+3+4+5 =15，图中黄色为最 小生成树。 3
例:铺设一个连接各个城市的光纤通信网络。 图中蓝色为最小生成树。 d 4
b a c d 7 6 2 f e 8 1 4 4 3 4 7 2 3 5 6 3 2 1 h g 例：铺设一个连接各个城市的光纤通信网络。 图中蓝色为最小生成树
破圈法求最小生成树 避圈法是贪婪地增加不构成回路的边,以 求得最小生成树 从另一个角度来考虑最小成树问题,由G的 圈(回路)最优条件,我们也可以在原连通权 图G中逐步删除构成回路中权最大的边,最后剩 下的无回略的生成子图为最小成树。我们把这 种方法称为“破圈法
破圈法求最小生成树 避圈法是贪婪地增加不构成回路的边，以 求得最小生成树。 从另一个角度来考虑最小成树问题，由G的 圈（回路）最优条件，我们也可以在原连通权 图G中逐步删除构成回路中权最大的边，最后剩 下的无回路的生成子图为最小成树。我们把这 种方法称为“破圈法