最小生成树-Kruskal（克鲁斯卡尔）算法+理解+证明；

关于最小生成树，我曾经理解过，然后上离散数学后又理解了一遍，所以就向想一下这个博客；主要是理解和证明；

.首先我们什么提出最小生成树概念：
设无向连通带权图G=<V,E,W>,T是G的一颗生成树，T的各边权之和称为T的权，记作W（T）。G的所有生成树中权最小的生成树称为G的最小生成树。

求最小生成树已经有许多种方法，这里介绍的是避圈法（Kruskal）；

怎样找出最小生成树：

设n阶无向连通图带权图G=<V,E,W>有m条边，不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大顺序排序，设e1,e2,e3…em;

取e1在T中，然后依次检查e1,e2,e3…em。若ej（j>=2）与已在T中的边不能构成回路，则取ej在T中，否则弃去ej。

算法停止时得到的T为G的最小生成树；
下面这个第一张图片是G无向连通图；第二张图片是T，即G的最小生成树；



理解了，那么我们就来证明一下这个算法的正确性；

1.首先，假设我们已经对所有边进行了排序，并且当前遍历到的边是连接点1和点3的边。

2.因为这条边是最小的边，而点1和点3在最小生成树中一定会直接或间接的相连，因此任何从点1到点3的路径都不小于这条边。如图，如果不走这条边就走1→2→3 或者1->4->3（而如果这样走显然会使得1→3的距离过大，而我们当前只讨论1→3的最优选项）。或者，我们可以假设一种情况：点1和点3之间有两条权值为0.25的边，间接的连接了点1和点3，那么这条路径显然比当前权值为1的边的权值小。但是我们是从小到大遍历边的，所以如果出现了这种情况，那么由于比权值为1的这条边小，那么他们必定已经被遍历。

由于那条路径已经被遍历过，那么这时候点1和点3就处于一个并查集了，也就是说我们不会再选择边权为3的这条边了。

3.因此我们可以证明出一个结论：图中权值最小的这条边必然要被选择。

4.假设我们已经选择了直接连接点1和点3的这条边，那么我们就可以对点1和点3进行缩点，由于最小生成树的性质（只要有路径连接两个任意结点即可），缩点对建图没有任何影响。

5.重复以上操作，直到边的数量等于点的数量减一（一个图的最小生成树的边的数量必定等于这个图的点的数量减一）即可得出最小生成树。

接下来就是上代码了：
由于时间关系先写到这，后再填坑；

这里一道是关于避圈法（Kruskal算法）的题解；
请点这里