有两种最小生成树生成算法，Kruskal,Prim
Kruskal算法是一种基于贪心方法的最小生成树算法。该算法初始将图 视为森林，图中的每一个顶点是一课独立的树。一颗树只与它的邻接 顶点中权值最小且不违反最小生成树属性（不构成环）的树之间建立 连边。
- 将所有的边按照权值进行非降序排序
- 选择权值最小的边
- 判断这条边构不构成环
- 构成环则放弃，下一条边
- 重复步骤二,直到所有顶点都被访问到，则算法停止
如何判断边构不构成环，可以选择Union-Find/并查集 的方法。
普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在生成树中的顶点（假设为 A 类），剩下的为另一类（假设为 B 类）。
对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。
然后找出 B 类中到 A 类中的顶点之间权值最小的顶点: 这一过程非常关键，我们可以借用cpp中基于红黑树实现 的multimap，key为边的权值，value为边的两个顶点，begin()指针是权值最小的map指针，我们可以判断两个顶点 是不是都在A类中，如果都在，则从map中删除这一项。如果指针的两个顶点都不在A类中，则跳过。如果指针的两个 顶点一个在A类中，一个在B中，则在B中的顶点转移到A中，同时map删除这一项，指针回到begin,进入洗一个循环。
代码只实现了Prim算法，不过这两个算法是相同的，后面再补充。
这里有一篇很好的文章，详细介绍了Kruskal和prim算法。可以作为参考
最小生成树的问题，简单得理解就是给定一个带有权值的连通图（连通网），从众多的生成树中筛选出权值总和最小的生成树，即为该图的最小生成树。
最经典的两个最小生成树算法：Kruskal 算法与 Prim 算法。两者分别从不同的角度构造最小生成树，Kruskal 算法从边的角度出发，使用贪心的方式选择出图中的最小生成树，而 Prim 算法从顶点的角度出发，逐步找各个顶点上最小权值的边来构建最小生成树的。
最小生成树问题应用广泛，最直接的应用就是网线架设、道路铺设。还可以间接应用于纠错的LDPC码、Renyi 熵图像配准、学习用于实时脸部验证的显著特征、减少蛋白质氨基酸序列测序中的数据存储，在湍流（turbulent）中模拟粒子交互的局部性，以及用于以太网桥接的自动配置，以避免在网络中形成环路。除此之外，最小生成树在聚类算法中也是应用广泛。