最小生成树

1.定义

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得 的 w(T) 最小，则此 T 为 G 的最小生成树。

用处例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

2.求法

核心是贪心，每次选择最短的且目前不联通的两点间一条边建，然后标记已经联通，具体的方式是并查集。即kruskal算法。

3.正确性的证明

** 第一步，我们证明按照kruskal算法操作一定能得到一颗生成树。 **

假设该算法得到的不是生成树，根据树的定义，就有两种情形，第一是得到的图是有环的，第二就是得到的图是不连通的。由于算法要求每次加入边都是无环的，所以第一种情形不存在，下面就只需证明第二种情形不存在即可。

假设得到的图是不连通的，则至少包含两个独立的的边集，假设其中一个为E，则E中边对应的所有点都无法到达其它边集对应的点（否则，根据算法定义，相应的联系边应被加入树中），而这与原图是连通的产生矛盾，因此，第二种情形也不可能存在。得证。

** 然后，我们证明这颗生成树是最小生成树。 **

假设图有n个顶点，则生成树一定具有n-1条边.由于图的生成树个数是有限的，所以至少有一棵树具有最小代价，假设该树为U。先做出如下假设：

1)得到的树为T。

2)U和T中不同的边的条数为k,其它n-1-k条边相同，这n-1-k条边构成边集E。；

3)在T中而不在U中的边按代价从小到大依次为a1，a2，...，ak。

4)在U中而不在T中的边按代价从小到大依次为x1，x2，...，xk。

现在我们通过把U转换为T（把T的边依次移入U中），来证明U和T具有相同代价。

首先，我们将a1移入U中，由于U本身是一棵树，此时任意加一条边都构成回路，所以a1的加入必然产生一条回路，且这条回路必然包括x1，x2，...，xk中的边。（否则a1与E中的边构成回路，而E也在T中，这与T中无回路矛盾。） 在这个回路中删除属于x1，x2，...，xk且代价最大边xi构成一个新的生成树V。

假设a1代价小于xi，则V的代价小于U，这与U是最小代价树矛盾，所以a1不可能小于xi。

假设a1大于xi，按照Kruskal算法，首先考虑代价小的边，则执行Kruskal算法时，xi应该是在a1之前考虑，而a1又在a2，...，ak之前考虑，所以考虑xi之前，T中的边只能是E中的边，而xi既然没加入树T，就说明xi必然与E中的某些边构成回路，但xi和E又同时在U中，这与U是生成树矛盾，所以a1也不可能大于xi。

因此，新得到的树V与T具有相同代价。

依次类推，把a1，a2，...，ak的边逐渐加到U中，最终得到的树（T)与U代价相同。

证明结束。