• 中文
    • English
  • 注册
  • 查看作者
    • Kruskal算法求最小生成树

      一.  前言

      Kruskal算法又称克鲁斯卡尔算法,在离散数学中又叫避圈法,是一种用来查找最小生成树的算法,由Joseph Kruskal在1956年发表,用来解决同样问题的还有Prim算法,我们先来引入最小生成树的概念

      二.  最小生成树

      设无向连通带权图G = <V,E,W>,T是G的一棵生成树,T的各边权之和称为T的权,记作W(T),G的所有生成树中权最小的生成树,称为G的最小生成树,最小生成树若有n个结点,则有n-1条边

      三.  Kruskal算法

      1.  设n阶无向连通带权图G = <V,E,W>有m条边,将m条边的权按照从小到大的顺序排列,设为e1,e2,……em

      2.  取e1 在T中,然后依次检查e2,e3……em,如果ej(j>=2)与已在T中的边不能构成回路,则取ej在T中,否则去掉ej

      3.  当算法停止时,得到的T就是G的最小生成树

      另外值得注意的是:

      使用不同的遍历图的方法,可以得到不同的生成树;

      从不同的顶点出发,也可能得到不同的生成树。

      四.  举例

      1.  用KruKal算法,求下图的最小生成树

      Kruskal算法求最小生成树

      2.  首先将权值从小到大排列:10 < 12 < 14 < 16 < 18 < 22 < 24 < 25 < 28

      3.  接下来,先取权值最小的10,如下图

      Kruskal算法求最小生成树

      4.  再取12,如下图

      Kruskal算法求最小生成树

      5.  再取14,如下图

      Kruskal算法求最小生成树

      6.  再取16,如下图

      Kruskal算法求最小生成树

      7.  再取18,但是我们发现加上18后,构成了一个回路,所以18不可取,如下图

      Kruskal算法求最小生成树

      8.  再取22,如下图

      Kruskal算法求最小生成树

      9.  再取24,但是我们发现加上24后,构成了一个回路,所以24不可取,如下图

      Kruskal算法求最小生成树

      10.  再取25,如下图

      Kruskal算法求最小生成树

      11.  再取28,但是我们发现加上28后,构成了一个回路,所以28不可取,至此,最小生成树完成,如下图

      Kruskal算法求最小生成树

    • 0
    • 2
    • 0
    • 7.4k
    • 请登录之后再进行评论

      登录
    • 0
      这样很简单,帮助很大。
    • 0
      帮助很大 谢谢
    • 赞助本站

      • 支付宝
      • 微信
      • QQ

      感谢一直支持本站的所有人!

      单栏布局 侧栏位置: