算法4.8 MST的Kruskal算法

  • 与Prim方法对比:Prim算法中树的生长都是通过连接一个新的顶点,而Kruskal算法中不同顶点可以先连成较小树,最后不同树之间合并
  • 描述:Kruskal算法每次将最小边加入MST中,新加入的边不会和已有边成环,知道树中有V-1条边
  • 命题:Kruskal算法可以得到任意加权连通图的最小生成树

证明:由定义,当前加入边不会和MST中边构成环,则为跨越树和树补两界的且按权重顺序选择的边,必然为权重最小横切边,则运用贪心算法,连续选边可得到完整MST

  • 数据结构:
    • 顶点情况:并查集UF,当uf.connected(v,w)则v-w失效
    • MST边:Queue mst,保存MST中的边
    • 横切边:使用优先队列MinPQ根据权重比较所有边

实现

  1. import edu.princeton.cs.algs4.UF;
  3. public class Kruskal {
  4.     private Queue<Edge> mst;
  6.     public Kruskal(EdgeWeightedGraph G){
  7.         mst = new Queue<>();
  8.         MinPQ<Edge> pq = new MinPQ<>(G.V());
  9.         for (Edge e: G.edges()) pq.insert(e);//开始在pq中加入所有边
  10.         UF uf = new UF(G.V());
  12.         while (!pq.isEmpty() && mst.size() < G.V()-1){
  13.             Edge e = pq.delMin();//最小权边
  14.             int v = e.either(), w = e.other(v);
  15.             if(uf.connected(v,w)) continue;//失效边
  16.             uf.union(v,w);
  17.             mst.enqueue(e);
  18.         }
  19.     }
  21.     public Iterable<Edge> edges(){ return mst;}
  22. }

算法分析

  • Kruskal算法计算连通加权无向图G(V,E)的最小生成树所需空间和E成正比,时间和ElogE(最坏)成正比

证明:算法开销在于使用所有边初始化MinPQ,最多E次比较,MinPQ中最多E条边,为最大空间,每次操作最多需要2lgE次比较,合计ElogE,其中UF的最多E次connected()和V次union()可忽略

  • Kruskal和Prim都不适用于有向图