最小生成树基础

【0】README

0.1） 本文总结于 数据结构与算法分析， 源代码均为原创， 旨在 review 最小生成树的基础知识；
0.2）了解本文的内容是 分析 Prim算法（普利姆算法）和 Kruskal算法（克鲁斯卡尔算法） 的前提；

【1】最小生成树（一句话，所有点相连的边的权值最小）

1.1）我们考虑的问题： 在一个无向图中找出一颗最小生成树。一个无向图G的最小生成树就是由该图的那些连接G 的所有顶点的边构成的树， 且其总价值最低。最小树存在，且仅当G是连通的。

Attention）

• A1）注意， 在最小生成树中边的条数为 |V|-1；最小生成树是一颗树， 因为它无圈；因为最小生成树包含每一个顶点，所以它是生成树；
• A2）此外，最小生成树显然包含图的所有顶点的最小的树；
• A3）应用： 如果我们需要用最少的电线给一所房子安装电路，我们就需要解决最小生成树问题；

1.2）对于任一生成树T， 如果将一条不属于 T的边e 添加进来，则产生一个圈；

• 1.2.1）如果从该圈中除去任意一条边， 则又恢复生成树的特性；
• 1.2.2）如果边e 的值比除去的边的值还低， 那么新的生成树的值就比原生成树的值低；
• 1.2.3）如果在建立生成树时所添加的边在所有避免成圈的边中值最小，那么最后得到的生成树的值不能再改进， 因为任意一条替代的边的值都大于等于已经存在于该生成树中的一条边的值；它指出， 对于最小生成树这种贪欲是成立的；

Attention）下面介绍两种方法以实现 最小生成树， 它们的区别在于最小（值的）边的选取上——Prim算法（普利姆算法）和 Kruskal算法（克鲁斯卡尔算法）