最小生成树

问题提出：
    要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。
问题分析：
    答案只能从生成树中找，因为要做到任何两个城市之间有线路可达，通信网必须是连通的；但对长度最小的要求可以知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。
结论：
    希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 —— 最小代价生成树。
    构造最小生成树的算法很多，其中多数算法都利用了一种称之为 MST 的性质。
    MST 性质：设 N = (V, E)  是一个连通网，U是顶点集 V的一个非空子集。若边 (u, v) 是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u, v) 的最小生成树。

（1）普里姆 (Prim) 算法

算法思想： 
    ①设 N=(V, E)是连通网，TE是N上最小生成树中边的集合。
    ②初始令 U={u_0}, (u_0∈V), TE={ }。
    ③在所有u∈U，u∈U-V的边(u,v)∈E中，找一条代价最小的边(u_0,v_0 )。
    ④将(u_0,v_0 )并入集合TE，同时v_0并入U。
    ⑤重复上述操作直至U = V为止，则 T=(V,TE)为N的最小生成树。

 
代码实现：

  

   

    

     

    
    

     

      void MiniSpanTree_PRIM(MGraph G,VertexType u)
     
    
   

    

     

    
    

     

          //用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
     
    
   

    

     

    
    

     

          //记录从顶点集U到V-U的代价最小的边的辅助数组定义；
     
    
   

    

     

    
    

     

          //closedge[j].lowcost表示在集合U中顶点与第j个顶点对应最小权值
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          int k, j, i;
     
    
   

    

     

    
    

     

          k = LocateVex(G,u);
     
    
   

    

     

    
    

     

          for (j = 0; j < G.vexnum; ++j)    //辅助数组的初始化
     
    
   

    

     

    
    

     

              if(j != k)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  closedge[j].adjvex = u;
     
    
   

    

     

    
    

     

                  closedge[j].lowcost = G.arcs[k][j].adj;    
     
    
   

    

     

    
    

     

      //获取邻接矩阵第k行所有元素赋给closedge[j!= k].lowcost
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          closedge[k].lowcost = 0;        
     
    
   

    

     

    
    

     

      //初始，U = {u};  
     
    
   

    

     

    
    

     

          PrintClosedge(closedge,G.vexnum);
     
    
   

    

     

    
    

     

          for (i = 1; i < G.vexnum; ++i)    \
     
    
   

    

     

    
    

     

      //选择其余G.vexnum-1个顶点，因此i从1开始循环
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              k = minimum(G.vexnum,closedge);        
     
    
   

    

     

    
    

     

      //求出最小生成树的下一个结点：第k顶点
     
    
   

    

     

    
    

     

              PrintMiniTree_PRIM(G, closedge, k);     //输出生成树的边
     
    
   

    

     

    
    

     

              closedge[k].lowcost = 0;                //第k顶点并入U集
     
    
   

    

     

    
    

     

              PrintClosedge(closedge,G.vexnum);
     
    
   

    

     

    
    

     

              for(j = 0;j < G.vexnum; ++j)
     
    
   

    

     

    
    

     

              {                                           
     
    
   

    

     

    
    

     

                  if(G.arcs[k][j].adj < closedge[j].lowcost)    
     
    
   

    

     

    
    

     

      //比较第k个顶点和第j个顶点权值是否小于closedge[j].lowcost
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     

                      closedge[j].adjvex = G.vexs[k];//替换closedge[j]
     
    
   

    

     

    
    

     

                      closedge[j].lowcost = G.arcs[k][j].adj;
     
    
   

    

     

    
    

     

                      PrintClosedge(closedge,G.vexnum);
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

（2）克鲁斯卡尔 (Kruskal) 算法

算法思想： 
    ①设连通网  N = (V, E )，令最小生成树初始状态为只有n个顶点而无边的非连通图，T=(V, { })，每个顶点自成一个连通分量。
    ②在 E 中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。
③依此类推，直至 T 中所有顶点都在同一连通分量上为止。
      
    最小生成树可能不惟一！

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/87823689