图算法-最小生成树

大家好，欢迎来到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依次执行然后依次递归

这样操作树的权重永远最小，且不会形成回路（因为另外一个顶点不在此树里面）

借住了贪心算法思想

实例

1. 某城市新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通
2. 各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里
3. 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?

性质：

1、连通图

1、满足所有的顶点，并且连接无环

2、每条边有权重（比如边的长短）

注意：所谓最小，指的是权重之和最小

几个感念

连通分量

针对图最小生成树的几种算法