欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

克鲁斯卡尔算法生成最小树(画图)

程序员文章站 2022-06-24 17:38:08
克鲁斯卡尔算法生成最小树(画图)(1)克鲁斯卡尔算法概念(2)实现思路(3)例题例题解题思路分析:1.根据信息画出这棵树的所有连通网2.我们根据权值的大小进行升序排序2.根据权值的大小依次连接顶点总结:(1)克鲁斯卡尔算法概念克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树(2)实现思路对于任意一个连通网的最小生成树来说,在要求总的权值最小的情况下,最直接的想法就是将连通网中的所有边按照权值大...

(1)克鲁斯卡尔算法概念

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树

(2)实现思路

对于任意一个连通网的最小生成树来说,在要求总的权值最小的情况下,最直接的想法就是将连通网中的所有边按照权值大小进行升序排序,从小到大依次选择。

克鲁斯卡尔算法的具体思路是:将所有边按照权值的大小进行升序排序,然后从小到大一一判断,条件为:如果这个边不会与之前选择的所有边组成回路,就可以作为最小生成树的一部分;反之,舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树;
可能概念有点难理解,看后面的例子就懂了。

(3)例题

克鲁斯卡尔算法生成最小树(画图)
答案为最后一张图
克鲁斯卡尔算法生成最小树(画图)

例题解题思路分析:

怎么得到的呢?
克鲁斯卡尔算法生成最小树(画图)

1.根据信息画出这棵树的所有连通网

我们知道该图是有7个顶点,12条边
根据信息我们先画出这棵树的所有连通网,如下图:
克鲁斯卡尔算法生成最小树(画图)

2.我们根据权值的大小进行升序排序

根据上图我们知道权值的大小按升序排序依次为:

3→4→5→6→8→9→10→12→15→18→20→25

2.根据权值的大小依次连接顶点

条件为:如果这个边不会与之前选择的所有边组成回路,就可以作为最小生成树的一部分;反之,舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
我们这个例子有7个顶点:所以我们连通网筛选出来 6 条边为止。

  1. 连接3号线
    3→4→5→6→8→9→10→12→15→18→20→25
    克鲁斯卡尔算法生成最小树(画图)

  2. 连接4号线
    3→4→5→6→8→9→10→12→15→18→20→25
    克鲁斯卡尔算法生成最小树(画图)

  3. 连接5号线
    3→4→5→6→8→9→10→12→15→18→20→25
    克鲁斯卡尔算法生成最小树(画图)

  4. 连接6号线时,我们发现,1,2,3这三个顶点形成了回路,舍弃这条线的连接
    3→4→5→6→8→9→10→12→15→18→20→25

  5. 连接8号线
    3→4→5→6→8→9→10→12→15→18→20→25
    克鲁斯卡尔算法生成最小树(画图)

  6. 连接9号线,我们发现,1,3,4,6这四个顶点形成了回路,舍弃这条线的连接
    3→4→5→6→8→9→10→12→15→18→20→25

  7. 连接10号线
    3→4→5→6→8→9→10→12→15→18→20→25
    克鲁斯卡尔算法生成最小树(画图)

  8. 连接12号线,我们发现,1,2,3,5这四个顶点形成了回路,舍弃这条线的连接
    3→4→5→6→8→9→10→12→15→18→20→25

  9. 连接15号线,我们发现,1,3,4这三个顶点形成了回路,舍弃这条线的连接
    3→4→5→6→8→9→10→12→15→18→20→25

  10. 连接18号线我们发现,1,2,5,6,4这五个顶点形成了回路,舍弃这条线的连接
    3→4→5→6→8→9→10→12→15→18→20→25

  11. 连接20号线
    3→4→5→6→8→9→10→12→15→18→20→25
    克鲁斯卡尔算法生成最小树(画图)

  12. 连接25号线,肯定形成回路,因为最小树已经生成,所有的顶点已经连通
    3→4→5→6→8→9→10→12→15→18→20→25
    最后就得到了最小树:是不是很简单呢!
    克鲁斯卡尔算法生成最小树(画图)

总结:

最小生成树的方法有:克鲁斯卡尔算法和普里姆算法,我们这里介绍了克鲁斯卡尔算法

克鲁斯卡尔算法:从边的角度求网的最小生成树,时间复杂度为O(eloge)。和普里姆算法恰恰相反,更适合于求边稀疏的网的最小生成树。

普里姆算法:该算法从顶点的角度为出发点,时间复杂度为O(n2),更适合与解决边的绸密度更高的连通网

代码实现我就不写了:可以看看其他博客主的实现

本文就你有帮助的,点个赞 给予渺小的博客主一个支持哦
克鲁斯卡尔算法生成最小树(画图)

本文地址:https://blog.csdn.net/qq_44667165/article/details/111852886