最小生成树(Minimum Cost Spanning Tree)，简称MST。
“我们把构造连通网的最小代价生成树称为最小生成树” 或 “给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树”
如何获得最小生成树“连通图”的个人解释：有N个端点，通过一定的规律或遵循某些约束将它们连接，形成连通图。
“权”的个人解释：端点与端点之间的连线所表示的值，比如可以是两点之间的距离（100公里）、完成任务或项目的工期（30天）等等。
以下通过一个案例来介绍获得最小生成树的算法和场景。
下图标明了六个城市（A~F）之间的公路（每条公路旁标注了其长度公里数）。为将部分公路改造成高速公路，各城市质检均可通过高速公路通达，至少要改造总计（）公里的公路，这种总公里数最少的改造方案共有（）个？
问题一解析 使用普里姆算法（Prim）详细步骤对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。 从所有uЄU，vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。
普里姆算法的运行效率只与连通网中包含的顶点数相关，而和网所含的边数无关。所以普里姆算法适合于解决边稠密的网，该算法运行的时间复杂度为：O(n2)。
如果连通网中所含边的绸密度不高，则建议使用克鲁斯卡尔算法求最小生成树。
1.任取一点，假设取端点A为起点。与A可连通的端点有BCEF，其连线的权值如下，取最小权值连线：AE，结果集为{AE}
| AB | AC | AE | AF |
|---|---|---|---|
| 300 | 400 | 200 | 300 |
2. 与端点A、E可连通的端点有BCF，其连线的权值如下，取最小权值连线：AB、AF，结果集为{AE、AB、AF}
| AB | AC | AF | EF |
|---|---|---|---|
| 300 | 400 | 300 | 400 |
3. 与端点A、B、E、F可连通的剩余端点有CD，其连线的权值如下，取最小权值连线：FD，结果集为{AE、AB、AF、FD}
| AC | BC | FD |
|---|---|---|
| 400 | 400 | 200 |
4. 与端点A、B、D、E、F可连通的剩余端点只有C，其连线的权值如下，取最小权值连线：CD，结果集为{AE、AB、AF、FD、CD}，此时已无剩余端点，得出结论最小权值为1300公里。
| AC | BC | DC |
|---|---|---|
| 400 | 400 | 300 |
详细步骤普里姆算法是从端点的角度求网的最小生成树，而克鲁斯卡尔算法是从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。
克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。
- 将原始图中的所有连线的权值按从小到大排序后，得到：
- AE : 200
- FD : 200
- AB : 300
- BF : 300
- AF : 300
- CD : 300
- AC : 400
- BC : 400
- CF : 400
- EF : 400
- 取上步中最小的连线作为结果集：{AE、FD}
- 从剩余的连线中取出最小的连线，考虑不能产生回路，则有以下几种结果：
- 上述3中方案的权值和都是1300，所以最少一共有3种改造方案。
更多信息可以参考一下资料学习。
https://www.cnblogs.com/ssyfj/p/9488723.html
https://my.oschina.net/guizimo/blog/4548037
https://www.cnblogs.com/wlzy/p/8695078.html
http://data.biancheng.net/view/40.html
http://data.biancheng.net/view/41.html
