kruskal 算法正确性的证明
作者带提高组的学生比较多，在教学最小生成树相关内容的时候（比如最小生成树的求解、唯一性等等…），学生的反馈通常都比较糟糕，所以这里整理一下我关于 kruskal 算法的一些理解。而 prim 的基本原理其实和 kruskal 类似，再加上篇幅不宜太长，这里就先不讨论了。
大多数 kruskal 算法的内容，都是基于其正确性的证明，我们需要明白为什么可以这样做，所以这里先聊一聊正确性的问题。
最小生成树（MST）问题
给定一张无向连通带权图GGG，生成树是指从GGG中选取部分边，构成一棵包含所有顶点且无环的树，生成树的边权和为所有边的权值之和。最小生成树（Minimum Spanning Tree, MST）是指在所有可能的生成树中，边权和最小的那棵（可能不唯一）。
（以上内容来自网络）
kruskal 算法的求解过程
- 将所有的边按照权值从小到大进行排序；
- 选择当前可用边里面，权值最小的边，尝试将其加入到生成树当中，这里我们通常使用并查集来进行判断，如果加入这条边会导致出现环，那么就跳过，否则将其加入到生成树当中；
- 重复步骤 2，直到生成树当中包含了所有顶点为止。
正确性证明
这里我们给无向连通图的每一条边一个编号，通过 kruskal 算法，我们得到了一个生成树TTT，这棵树包含n−1n - 1n−1条边。
接下来我们使用反证法来证明 kruskal 算法的正确性，假设存在一个与TTT不同的生成树T′T'T′，而这棵生成树的边权之和要小于原本的TTT。
然后这里有两个性质：
- 我们可以把T′T'T′看作删除了TTT中的某一些边，然后添加了一些其他的边得到的（当然了这些边全是GGG中的）；
- 对应的，我们可以把生成树T′T'T′的方法理解为：先选择无向图中权值较大的一些边，而不是最小的，直到生成树当中包含了所有顶点为止（跟 kruskal 恰好相反）。
我们先来看第一个性质：
假设我们删除了TTT中的一些边，这些边为a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak。
在我们删除a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak之后，整棵树被拆分成了若干棵子树，下一步，我们需要再按照其他的方式（使得生成树权值之和变得更小）再把所有的子树重新连接起来。
那么这里其实我们可以视这些子树为一个一个的点，重新做一遍最小生成树问题。
例如上图，在删除 1 和 5 两条边之后，我们可以认为整棵树只有三个点，分别对应三棵子树，需要再添加两条边使得他们连起来。
那么这里要处理的问题变成了，给你一个无向图，然后给你两种完全不同的边的方案，分别为a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak和b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk，其中a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak是按照 kruskal 算法求解的，而b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk是按照性质 2 所说的方法求解的。
我们需要证明不存在任何一种性质 2 的方法，使得生成树的边权之和比 kruskal 算法的边权之和要小。
剩下来的就好办了，我们把两种方案的边按照权值从小到大进行排序，a1a_1a1和b1b_1b1分别表示两种方案中权值最小的边。根据性质 2，显然a1a_1a1要小于b1b_1b1，换而言之a1a_1a1比b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk都要小。
假设选择b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk这些边生成的树长成下面的样子（黑色部分）：
而红色的边表示a1a_1a1，只要我删除从 x 到 y 路径上的任意一条边，换成a1a_1a1，就可以得到一个比T′T'T′边权和更小的生成树 —— 因为a1a_1a1比b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk都要小。
所以我们证明了不存在任何一种性质 2 的方法，使得生成树的边权之和比 kruskal 算法的边权之和要小。
那么到此为止就证明了 kruskal 算法的正确性。
)
