大家好，欢迎来到IT知识分享网。
一、定义
(Minimum Cost Spanning Tree)，简称 MST。给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树
1、克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为边数），适合于求边稀疏的网的最小生成树 。克鲁斯卡尔算法从另一途径求网的最小生成树。其基本思想是：假设连通网G，令最小生成树的初始状态为只有n个顶点而无边的非连通图T，概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。说白了，优先先选出全体边里最短的那几条，然后如果各分量还没连起来，就继续选择剩余没被选择的边里最短的，直到全部节点都连接在一起。
原文链接：https://blog.csdn.net/_/article/details/
它的时间复杂度为O（eloge）e为边数）
方法：
1、集合是一个森林，每个顶点都是一棵树，都是一个强连通量
2、所有的边进行排序，选择权重最小的边
3、针对边的两个顶点判断是否属于一个联通量，不属于进行合并，合并成一个联通量，此边是寻找的边
4、循环所有的边
思路
1、有n个小联通分量（顶点）其实就是用不同标记区分不同的集合（连通分量）
2、选择权重最小边的两个顶点，然后针对不同的联通分量进行合并
比如顶点a的联通量是他自己也可以用其他的代替，用自己区分其他很简单
a与顶点b合并之后，联通量都变成b
c与d合并之后联通量都转换为d
ac合并都转换成d
代码
这里一定要理解好Vexset数组的作用和意义。如果这个理解不好，就像prim算法不理解close数组一样，核心算法就理解不了了。
Vexset是以下标i表示节点，以数组的值表示该点的连通量。
如：Vexset[1] = 0，Vexset[0] = 0.表示B节点和A节点是同一个连通量（B的下标为1，A的下标为0）。
代码执行过程：
1、初始化边集合：把图里全部边加入边集合（集合里边的数量就是图里边的数量）。
2、初始化辅助数组Vexset：每个节点自己属于一个连通量（毕竟刚开始谁都没连接谁是吧）。
3、将边集合按照边权值从小到大排序，让循环操作从小边到大边的顺序进行选择。
4、循环获取每一条边的起点和终点。
5、如果起点和终点不是同一个连通分量，就把两个点连起来（合并连通量）。
6、全部点同属一个连通分量，循环结束。
2、prim（普里姆算法）算法
整体思想是，创建一棵树，找到一个安全边加入此树
方法
1、树是一个集合、顶点是一个集合
2、选择一个顶点根节点放到树里面，顶点集合删除此顶点
两个顶点不在一个集合肯定构不成环
3、寻找树所有的顶点所对应的边并进行权重排序
4、找到在集合顶点中的权重最小的边
5、树中加入此顶点，在集合中删除此顶点
4、3-5依次执行然后依次递归
这样操作树的权重永远最小，且不会形成回路（因为另外一个顶点不在此树里面）
借住了贪心算法思想
实例
- 某城市新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通
- 各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里
- 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
性质：
1、连通图
1、满足所有的顶点，并且连接无环
2、每条边有权重（比如边的长短）
注意：所谓最小，指的是权重之和最小
几个感念
连通分量
针对图最小生成树的几种算法
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/93236.html
