最小生成树

最小生成树的ＭＳＴ性质：

假设Ｇ＝（Ｖ，Ｅ）是一个无向连通网，Ｕ是顶点集Ｖ的一个非空子集。若（ｕ，ｖ）是一条具有最小权值的边，其中ｕ属于Ｕ，ｖ属于Ｖ－Ｕ，则必存在一棵包含边（ｕ，ｖ）的最小生成树。

证明：现在随机生成一棵生成树Ｔ，把V分成U和V - U两个集合，现在已经有一棵生成树T了，所以在U和V - U之间一定有一条边连着，所以这种情况下V - U中的所有点一定是互相连通的，（u，v）这条边权最小，但是此刻并没有连着。那么就是V - U中的另一条边连接着这两个点集。那么假如把这条边换成（u ，v）了，一定比T的总权和小。

结合反证法：假设网N的任何一棵最小生成树都不包含（u，v）。设T是连通网上的一棵最小生成树，当将边（u，v）加入到T中时，由生成树的定义，T中必存在一条包含（u，v)的回路。另一方面，由于T是生成树，则在T上必存在另一条边（u’，v’），其中u’∈U，v’∈V - U，且u和u’之间，v和v’之间均有路径相通。删去边（u’，v’），便可消除上述回路，同时得到另一棵生成树T’。因为（u，v）的代价不高于（u’，v’），则T’的代价亦不高于T，T’是包含（u，v）的一棵最小生成树，和假设矛盾。

普里姆（Ｐｒｉｍ）算法和克鲁斯卡尔（Ｋｒｕｓｋａｌ）算法

是利用ＭＳＴ性质构造最小生成树的经典算法。
Ｐｒｉｍ算法适用于稠密图，采用加点法方式实现，由最初的一个顶点找到符合条件的全部顶底和边，而Ｋｒｕｓｋａｌ算法则适用于稀疏图，由最初的ｎ个无边的顶点按照边排序规则（依次从小到大）来考察边，生成最小生成树。

Ｐｒｉｍ算法伪代码实现（复杂度：Ｏ（ｎ２））：

１．初始化：Ｕ＝｛ｖ０｝；ＴＥ＝｛　｝；
	２．重复下述操作直到Ｕ＝Ｖ：
		２．１．在Ｅ中寻找最短边（ｕ，ｖ），且满足ｕ属于Ｕ，ｖ属于Ｖ－Ｕ；
		２．２．Ｕ＝Ｕ＋｛ｖ｝
		２．３．ＴＥ＝ＴＥ＋｛（ｕ，ｖ）｝；

显然，Ｐｒｉｍ算法是利用如何找到连接Ｕ和Ｖ－Ｕ的最短边来扩充生成树Ｔ。
Ｋｒｕｓｋａｌ算法伪代码实现（复杂度：Ｏ（ｅｌｏｇ２　ｅ））：
（实质是使生成树以一种随意的方式生长，初始化时每个顶底构成一棵生成树，然后每生长一次就对两棵树合并，到最后合并成一棵树）

１．初始化：Ｕ＝Ｖ；ＴＥ＝｛　｝；
２．重复下述步骤直到Ｔ中的连通分量个数为１：
２．１．在Ｅ中寻找最短边（ｕ，ｖ）；
２．２．如果顶底ｕ，ｖ位于Ｔ的两个不同连通分量，则
	２．２．１．将（ｕ，ｖ）并入ＴＥ；
	２．２．２．将这两个连通分量合并为一个
２．３．在Ｅ中标记（ｕ，ｖ），使得（ｕ，ｖ）不参加后续最短边的选取。