• 中文
    • 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.7k
  • 请登录之后再进行评论

    登录
  • 0
    这样很简单,帮助很大。
  • 0
    帮助很大 谢谢
  • 单栏布局 侧栏位置: