克鲁斯卡尔算法生成最小树（画图）
克鲁斯卡尔算法生成最小树（画图）
（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 条边为止。
-
连接3号线
3→4→5→6→8→9→10→12→15→18→20→25 -
连接4号线
3→4→5→6→8→9→10→12→15→18→20→25 -
连接5号线
3→4→5→6→8→9→10→12→15→18→20→25 -
连接6号线时，我们发现，1，2，3这三个顶点形成了回路，舍弃这条线的连接
3→4→5→6→8→9→10→12→15→18→20→25 -
连接8号线
3→4→5→6→8→9→10→12→15→18→20→25 -
连接9号线，我们发现，1，3，4，6这四个顶点形成了回路，舍弃这条线的连接
3→4→5→6→8→9→10→12→15→18→20→25 -
连接10号线
3→4→5→6→8→9→10→12→15→18→20→25 -
连接12号线，我们发现，1，2，3，5这四个顶点形成了回路，舍弃这条线的连接
3→4→5→6→8→9→10→12→15→18→20→25 -
连接15号线，我们发现，1，3，4这三个顶点形成了回路，舍弃这条线的连接
3→4→5→6→8→9→10→12→15→18→20→25 -
连接18号线我们发现，1，2，5，6，4这五个顶点形成了回路，舍弃这条线的连接
3→4→5→6→8→9→10→12→15→18→20→25 -
连接20号线
3→4→5→6→8→9→10→12→15→18→20→25 -
连接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