最小生成树

0x00 什么是最小生成树

​ 树：一定连通，且没有回路，v个顶点，一定有v-1条边

​ 生成树：包含全部顶点，v-1条边都在图里，向生成树中任加一条边都一定构成回路

​ 最小：边的权重和最小

​ 最小生成树（minimum spanning tree）存在<=>图连同

0x01 贪心算法

​ 每一步都选最好的解法

​ 1 只能用图里有的边

​ 2 正好用v-1

​ 3 不能形成回路

​ prim 算法：

​

1dist初始化 如果节点与根节点直接相连就初始化为对应权重，否则为正无穷，被收录则距离为0

2如何存树，用静态链表（数组保存子或者父节点） 保存父节点

3当这样的v不存在时 有两种可能 一 节点全部收录 二 剩下的节点的dist都是正无穷（不连通），所以突出循环后要判断收录的节点数目

4 如果 未收录顶点的最小者 用遍历，则时间复杂度为O(V^2+E) 适合稠密图

​ Kruskal算法：将森林合并成树

初始状态下认为每个节点都是一棵树，然后不断选最小权重边将两棵树合并成一棵树，但是该边不得使原来的树产生回路（通过集合的运算，如果该边的两个顶点处于同一棵树，也就是在同一个集合，就是回路。所以一开始合并树的时候要合并对应集合）。

​

按照图上 用最小堆和并查集，时间复杂度为O（eloge）,适合稀疏图（相比较v^2+e）（e接近v，比v2快）