新建 文本文档 (2).txt

克鲁斯卡尔(Kruskal)算法 （1）算法思想（2）算法特点（3）Kruskal算法的抽象描述（4）用Kruskal算法构造最小生成树的过程（5）算法分析

6、克鲁斯卡尔(Kruskal)算法
（1）算法思想
　　①T的初始状态
   　   只有n个顶点而无边的森林T=(V，￠ )
　　②按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST
注意：
    　安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树
    　因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。

（2）算法特点
    　该算法的特点是：当前形成的集合T除最后的结果外，始终是一个森林。

（3）Kruskal算法的抽象描述
  KruskalMST(G){//求连通网G的一棵MST
     T=(V，￠)； //初始化，T是只含n个顶点不包含边的森林
    依权值的递增序对E(G)中的边排序，并设结果在E[0..e-1]中
    for(i=0;i<e;i++) { //e为图中边总数
        取E[0．．e-1)中的第i条边(u，v)；
         if u和v分别属于T中两棵不同的树then
            T=T∪{(u，v)}；//(u，v)是安全边，将其加入T中
         if T已是一棵生成树then
      ``         return T；
        }//endfor
       return T；
   } 

（4）用Kruskal算法构造最小生成树的过程
    　用Kruskal算法构造最小生成树的过程【参见动画演示】


（5）算法分析
    　该算法的时间复杂度为O(elge)。
    Kruskal算法的时间主要取决于边数。它较适合于稀疏图。