寻找带权图的最小连通：最小生成树

出现背景

树就是没有回路的图

for无向图

对于不带权的图，想找到一个最小连通边集合，很简答，可以使用生成树，n-1条边可以做到，不唯一

对于带权的图，想找到权最小的生成树，称之为最小生成树

最小生成树性质

1、最小生成树不是唯一的，比如权值均相等问题退化到生成树，因为生成树不唯一，所以最小生成树不唯一

2、最小生成树的边的权值之和总是唯一的，因为如果不唯一，那么必有一个更小，更大的那个就不叫作最下生成树了

3、最小生成树的边数为顶点数减1，因为生成树有这个性质，所以最小生成树也有

下面介绍找到一个图的最小生成树的两种算法

Prim算法（优先找小点）

1、任意找个点

2、找最近的第二个点和连接边，组成点集

3、找点集最近的点和连接边，重复直到n-1条

4、所得点集线集即为最小生成树

时间复杂度O(|V|^2)，V是点集

Kruskal算法（优先找小边）

1、将边集放入堆中排序

2、抽出最小权边加入边集，如果构成回路舍弃，不构成回路加入

3、反复执行n-1次

4、所得边集即为最小生成树

时间复杂度O(|E|log|E|)，E为边集

在边稀疏，点较多的情况下更好用