温习Algs4 (五):并查集, 最小生成树

落日映苍穹つ 2022-04-11 11:11 198阅读 0赞

### 并查集, 带权图和最小生成树 ###

*  并查集
 *   *  UnionFind.java
 *  带权边和带权图
 *   *  WeightedEdge.java
     *  EdgeWeightedGraph.java
 *  最小生成树
 *   *  API
     *   *  MST.java
     *  Prim算法
     *   *  Prim.java
     *  Kruskal 算法
     *   *  Kruskal.java
     *  复杂度分析

# 并查集 #

英文名 Union Find, (UF). 是一个基于森林的数据结构, 支持的操作是

1.  连接两个节点
2.  判断两个节点是否相连

上述两个操作的时间复杂度接近 *O(1)* (经过了 *带权比较* 和 *路径压缩* 的优化), 空间复杂度为 *O(N)*

具体实现方式是: 每个节点一开始都是一棵树, 即初始状态是一个森林. 维护一个数组 *root*, 用来存储每个节点所属的树的根节点, 判断两个节点是否相连就是判断两个节点所在的树是否是同一个根; 连接操作即是将一个根节点成为另一个根节点的子节点.

## UnionFind.java ##

/****************************************************************************** * Compilation: javac UnionFind.java * Execution: java UnionFind * Author: Chenghao Wang ******************************************************************************/
    
    public class UnionFind { 
        private int[] weight;
        private int[] root;
    
        UnionFind() {  }
        UnionFind(int size) { 
            root = new int[size];
            weight = new int[size];
    
            for (int i = 0; i < size; i++) { 
                root[i] = i;
                weight[i] = 1;
            }
        }
    
        private int getRoot(int v) { 
            int w = v;
            while (w != root[w]) { 
                w = root[w];
            }
            root[v] = w;
            return w;
        }
    
        public boolean find(int v, int w) { 
            return getRoot(v) == getRoot(w);
        }
    
        public void union(int v, int w) { 
            int rootV = getRoot(v);
            int rootW = getRoot(w);
            if (rootW == rootV) return;
            if (weight[rootV] > weight[rootW]) { 
                weight[rootV] += weight[rootW];
                root[rootW] = rootV;
            } 
            else { 
                weight[rootW] += weight[rootV];
                root[rootV] = rootW;
            }
        }
    }

# 带权边和带权图 #

无须赘述

## WeightedEdge.java ##

/****************************************************************************** * Compilation: javac WeightedEdge.java * Execution: java WeightedEdge * Author: Chenghao Wang ******************************************************************************/
    
    public class WeightedEdge implements Comparable<WeightedEdge> { 
        private int u;
        private int v;
        private double weight;
    
        WeightedEdge() {  }
        WeightedEdge(int u, int v, double weight) { 
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    
        public int either() { 
            return u;
        }
    
        public int other(int x) { 
            if (x == u) return v;
            else return u;
        }
    
        public double weight() { 
            return weight;
        }
    
        @Override
        public int compareTo(WeightedEdge other) { 
            if (weight < other.weight) return -1;
            if (weight > other.weight) return +1;
            return 0;
        }
    
        @Override
        public String toString() { 
            return String.format("%d - %d (%.2f)\n", u, v, weight);
        }
    }

## EdgeWeightedGraph.java ##

/****************************************************************************** * Compilation: javac EdgeWeightedGraph.java * Execution: java EdgeWeightedGraph * Author: Chenghao Wang ******************************************************************************/
    import java.util.Scanner;
    
    public class EdgeWeightedGraph { 
        private int vertexCount;
        private int edgeCount;
        private Bag<WeightedEdge>[] adj;
        private Bag<WeightedEdge> edges;
    
        EdgeWeightedGraph() {  }
        EdgeWeightedGraph(int vertexCount) { 
            this.vertexCount = vertexCount;
            edgeCount = 0;
            edges = new Bag<WeightedEdge>();
            adj = (Bag<WeightedEdge>[]) new Bag[vertexCount];
            for (int i = 0; i < vertexCount; i++) { 
                adj[i] = new Bag<WeightedEdge>();
            }
        }
    
        EdgeWeightedGraph(Scanner scan) { 
            this(scan.nextInt());
            int e = scan.nextInt();
            for (int i = 0; i < e; i++) { 
                int u = scan.nextInt();
                int v = scan.nextInt();
                double w = scan.nextDouble();
                addEdge(u, v, w);
            }
        }
    
        public int V() { 
            return vertexCount;
        }
    
        public int E() { 
            return edgeCount;
        }
    
        public void addEdge(int u, int v, double w) { 
            WeightedEdge edge = new WeightedEdge(u, v, w);
            adj[u].add(edge);
            adj[v].add(edge);
            edgeCount++;
            edges.add(edge);
        }
    
        public void addEdge(WeightedEdge edge) { 
            int u = edge.either();
            int v = edge.other(u);
            adj[u].add(edge);
            adj[v].add(edge);
            edgeCount++;
            edges.add(edge);
        }
    
        public Iterable<WeightedEdge> adj(int v) { 
            return adj[v];
        }
    
        public Iterable<WeightedEdge> edges() { 
            return edges;
        }
    
        @Override
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            sb.append("<EdgeWeightedGraph>\n");
            for (int i = 0; i < vertexCount; i++) { 
                for (WeightedEdge e : adj[i]) { 
                    if (e.other(i) < i) continue;
                    sb.append(" " + e.toString());
                }
            }
            sb.append("</EdgeWeightedGraph>\n");
            return sb.toString();
        }
    
        public static void main(String[] args) { 
            EdgeWeightedGraph g = new EdgeWeightedGraph(new Scanner(System.in));
            System.out.println(g);
        }
    }

# 最小生成树 #

英文名 Minimum Spanning Tree(MST). 这里介绍两个算法, 分别是**Prim**算法和**Kruskal**算法. 首先介绍MST的API:

## API ##

### MST.java ###

/****************************************************************************** * Compilation: javac MST.java * Execution: java MST * Author: Chenghao Wang ******************************************************************************/
    
    public abstract class MST { 
        protected EdgeWeightedGraph g;
        protected Bag<WeightedEdge> edges;
        protected double weight;
    
        MST() {  }
        MST(EdgeWeightedGraph g) { 
            this.g = g;
            edges = new Bag<WeightedEdge>();
            weight = 0;
        }
    
        public Iterable<WeightedEdge> edges() { 
            return edges;
        }
    
        public double weight() { 
            return weight;
        }
    }

## Prim算法 ##

Prim算法的思想基于最小生成树的割集定理:

将一张图分为任意两部分(割集), 如下图, 分为 {A1, A2} 和 {B1, B2} 两部分,
    两部分之间共有e2, e3两条边连接. 那么min{e2, e3}必在MST中.

上面的定理可以自己好好想想.  
Prim算法从任意一点开始逐步建立生成树, 每次取**已建立的树**和**图的剩余部分**两个割集, 然后将连接两个割集的所有边中权重最小的加入到MST中.

### Prim.java ###

/****************************************************************************** * Compilation: javac Prim.java * Execution: java Prim * Author: Chenghao Wang ******************************************************************************/
    
    public class Prim extends MST { 
        private IndexPQ<WeightedEdge> pq;
        private boolean[] mark;
    
        Prim() {  }
        Prim(EdgeWeightedGraph g) { 
            super(g);
            pq = new IndexPQ<WeightedEdge>(g.V(IndexPQ.MIN_PQ));
            mark = new boolean[g.V()];
            visit(0);
            int count = 0;
            while (count < (g.V() - 1)) { 
                int v = pq.pop();
                WeightedEdge e = pq.getValue(v);
                edges.add(e);
                visit(v);
                weight += e.weight();
                count++;
            }
        }
    
        private void visit(int v) { 
            mark[v] = true;
            for (WeightedEdge e : g.adj(v)) { 
                int next = e.other(v);
                if (mark[next]) continue;
                if (!pq.contains(next)) { 
                    pq.push(next, e);
                } else if (pq.getValue(next).weight() > e.weight()) { 
                    pq.change(next, e);
                }
            }
        }
    }

## Kruskal 算法 ##

Kruskal算法是我最喜欢的一个算法, 因为其十分简单:

*  将所有边按照权重从小到大排序
 *  依次遍历每个边, 如果加入这个边不会构成一个环, 那么就加入到MST中

其中排序可以用优先级队列实现, 检查是否构成环可以用并查集实现

### Kruskal.java ###

/****************************************************************************** * Compilation: javac Kruskal.java * Execution: java Kruskal * Author: Chenghao Wang ******************************************************************************/
    
    public class Kruskal extends MST { 
        private UnionFind uf;
        private PQ<WeightedEdge> pq;
    
        Kruskal() {  }
        Kruskal(EdgeWeightedGraph g) { 
            super(g);
    
            uf = new UnionFind(g.V());
            pq = new PQ<WeightedEdge>(PQ.MIN_PQ);
    
            for (WeightedEdge e : g.edges()) { 
                pq.push(e);
            }
    
            int count = 0;
            while (count < (g.V() - 1)) { 
                WeightedEdge e = pq.pop();
                int u = e.either();
                int v = e.other(u);
                if (uf.find(u, v)) continue;
                uf.union(u, v);
                edges.add(e);
                weight += e.weight();
                count++;
            }
        }
    }

## 复杂度分析 ##

*  Prim: *O(E logV)*
 *  Kruskal: *O(E logE)*

因为O(logE) = O(log V ( V − 1 ) 2 \\frac\{V(V-1)\}\{2\} 2V(V−1)) = O(log V 2 V^2 V2) = O(logV), 所以二者的复杂度相似.