MST(Minimum Spanning Tree)最小生成树
最小生成树是指一个加权图的具有最小权的连通生成子图.
由于在所有连通生成子图中, 生成树的边数最少, 因此就是具有最小权的连通生成子树.
寻找最小生成树有: Kruskal 算法、Prim 算法
Kruskal 算法的思想是, 程序管理的是一些连通子树的集合, 每次在添加新的边时, 考虑的是是否会形成环, 若不形成环, 则添加.
Prim 算法的思想是: 既然最终要得到的是最小生成树, 我们可以通过一条边接着一条边的生长方式形成最后的权最小的生成树.
从上面的两种思想, 可以看到, 最小生成树的生成算法本质上只有这两种.
Kruskal 算法的 C++ 实现:
http://www.technical-recipes.com/2012/kruskals-algorithm-in-c/
https://www.sanfoundry.com/cpp-program-find-mst-kruskals-algorithm/