MST性质（用于构造最小生成树）

描述：假设N=（V，{E}）是一个连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边（u，v）的最小生成树。

证明：

       假设网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）的一棵最小生成树。由此和假设矛盾。

Prim算法：

    假设 N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u_o}（u_o∈V），TE{}开始，重复执行下述操作：在所有u∈U，v∈V-U的边（u，v）∈E中找一条代价最小的边（u_o，v_o）并入集合TE，同时v_o并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生产数。

 

Kruskal算法：

    假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。