最小生成树详解

最小生成树

1、 最小生成树

    　对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：

 这里:

    　TE表示T的边集

    　w(u，v)表示边(u，v)的权。

    　权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。

2、生成树和最小生成树的应用

    　生成树和最小生成树有许多重要的应用。

【例】网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

3、最小生成树性质（MST性质）

（1）MST性质

    　最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。

（2）MST性质的证明

    　为方便说明，先作以下约定：

　　①将集合U中的顶点看作是红色顶点，②而V-U中的顶点看作是蓝色顶点，③连接红点和蓝点的边看作是紫色边，④权最小的紫边称为轻边(即权重最"轻"的边)。于是，MST性质中所述的边(u，v)就可简称为轻边。

　　用反证法证明MST性质：

　　假设G中任何一棵MST都不含轻边(u，v)。则若T是G的一棵MST，则它不含此轻边。

    由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边(u'，v')连接红点集和蓝点集，否则u和v不连通。当把轻边(u，v)加入树T时，该轻边和P必构成了一个回路。删去紫边(u'，v')后回路亦消除，由此可得另一生成树T'。

   　 T'和T的差别仅在于T'用轻边(u，v)取代了T中权重可能更大的紫边(u'，v')。因为w(u，v)≤w(u'，v')，所以

    w(T')=w(T)+w(u，v)-w(u'，v')≤w(T)

故T'亦是G的MST，它包含边(u，v)，这与假设矛盾。

    　所以，MST性质成立。

4、求MST的一般算法描述

    　求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边(u，v)，最终生成一棵含n-1条边的MST。

    　当一条边(u，v)加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。

    　用伪代码可将算法描述为：

  GenerieMST(G){//求G的某棵MST

     T〈-￠； //T初始为空，是指顶点集和边集均空

     while T未形成G的生成树 do{

         找出T的一条安全边(u，v)；//即T∪{(u，v)}仍为MST的子集

         T=T∪{(u，v)}； //加入安全边，扩充T

      }

     return T； //T为生成树且是G的一棵MST

   }

  注意：

    　下面给出的两种求MST的算法均是对上述的一般算法的求精，两算法的区别仅在于求安全边的方法不同。

    　为简单起见，下面用序号0，1，…，n-1来表示顶点集，即：

　　V(G)={0，1，…，n-1}，

　　G中边上的权解释为长度，并设T=(U，TE)。

5、普里姆(Prim)算法

（1）算法思想

    　T=(U，TE)是存放MST的集合。

　　①T的初值是({r}，￠)

　　  即最小生成树初始时只有一个红点r，没有红边。

　　②T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树

    　⒈选择紫边集中一条轻边并扩充进T

　　⒉将轻边连接的蓝点改红点

　　⒊将轻边改红边

    　⒋修改紫边集

（2）较小紫边集的构造

    　若当前形成的T中有k个顶点，|U|=k，|V-u|=n-k，故可能的紫边数目是k(n-k)。从如此大的紫边集中选择轻边是低效的。因此，必须构造较小的紫边集。

    　对于每个蓝点v ∈V-U，从v到各红点的紫边中，只有最短的那一条才有可能是轻边。因此，只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。

（3）候选紫边集合的修改

    　当把轻边(u，v)扩充到T时，因为v由蓝变红，故对每个剩余的蓝点j，边(v，j)就由非紫边变为紫边，这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。因此，用长度更小的新紫边取代那些原有的最短紫边。

（4）Prim算法的伪代码描述

 PrimMST(G，T，r){

  //求图G的以r为根的MST，结果放在T=(U，TE)中

    InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)

    for(k=0；k<n-1；k++){ //求T的n-1条树边

        (u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；

         T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U

        ModifyCandidateSet(…)； //根据新红点v调整候选轻边集

      } 

   }