最小生成树的定义

最小生成树(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

问题二解析

使用克鲁斯卡尔算法（Kruskal）

普里姆算法是从端点的角度求网的最小生成树，而克鲁斯卡尔算法是从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。


克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。


判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

详细步骤

1. 将原始图中的所有连线的权值按从小到大排序后，得到：
   • AE : 200
   • FD : 200
   • AB : 300
   • BF : 300
   • AF : 300
   • CD : 300
   • AC : 400
   • BC : 400
   • CF : 400
   • EF : 400
2. 取上步中最小的连线作为结果集：{AE、FD}
   
3. 从剩余的连线中取出最小的连线，考虑不能产生回路，则有以下几种结果：
   
   
   
4. 上述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