动态连通性问题算法实现及优化

首先定义算法的API

1.好了，API已经定义好了，下面可以实现这个API，下面是第一个版本。实现思想是利用判断id[q]和id[p]是否相等来判断它们是否在同一个连通分量中。它的缺点是一般无法处理大规模问题，因为每次调用它都需要扫描一次数组，对于最终值得到少量连通分量的问题运行时间是平方级别的。

public class UnionFind {
    private int count;//记录连通分支数
    private int[] id;
    public UnionFind(int N){
        count = N;
        id = new int[N];
        for(int i = 0;i<N;i++)//完成将id初始化0~N-1
            id[i] = i;
    }
    public int find(int p){
        return id[p];
    }
    public int getCount(){
        return count;
    }
    public boolean connected(int p,int q){
        return id[p] == id[q];
    }
    public void union(int p, int q){//缺点：一般无法处理大规模问题，因为每次调用它都需要扫描一次数组，对于最终值得到少量连通分量的问题运行时间是平方级别的
        int pID = id[p];
        int qID = id[q];
        if(pID == qID) //思路：利用判断id[q]和id[p]是否相等来判断它们是否在同一个连通分量中
            return;//如果相等就什么也不做，因为它们本来就在一个连通分支里面
        for(int i = 0;i<id.length;i++){
            if(id[i] == pID)
                id[i] = qID;//将p所在的连通支路全部改为q，合并两个连通分支
        }
        count--;//合并之后因为连通分支数少一，所以减一
    }
}
复制

2.上面的那个算法不适用与大数据处理，原因是对于最终得到的连通分量问题的运行时间是平方级别的。下面的这个算法它优化了union（）方法，并修改了find（）方法以配合union（）方法的使用。它的设计思想是定义与之前不同的数据结构，每个触点所对应的id[]元素都是同一个分量中的另一个触点的名称（也有可能是它自己）——我们将这种联系称为链接。每个连通分量都有一个根触点。根触点的特点是id[i] = i。这种数据结构使得union（）在最坏情况下得到的结果是平方级别的，一般情况下是线性对数级别的。而find（）方法的运行时间取决于数的高度。

public class QuickUnion {
    private int count;//记录连通分支数
    private int[] id;
    public QuickUnion(int N){
        count = N;
        id = new int[N];
        for(int i = 0;i<N;i++)//完成将id初始化0~N-1
            id[i] = i;
    }
    public int find(int p){
        while(p != id[p])
            p = id[p];
        return p;//返回连通标号
    }
    public int getCount(){
        return count;
    }
    public boolean connected(int p,int q){
        return find(p) == find(q);
    }
    public void union(int p, int q){//最坏情况下得到的连通分量运行时间是平方级别的
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot)
            return;
        id[pRoot] = qRoot;
        count--;
    }
}
复制

3.下面是第三种方法实现，它进一步优化了第二种实现，使得在最坏情况下union（）也保持线性对数级别的运行时间。设计思想是在union（）中不是随意将一棵树链接到另一棵树中，而是通过添加一个数组来记录每颗数的大小，将较小的一颗链接到较大的一颗树上。我们将它称为加权quick-union算法。

public class WeightedQuickUnion {
    private int[] id;//父链接数组，由触点作为缩引
    private int[] sz;//存储各个触点具有的数据个数
    private int count;
    public WeightedQuickUnion(int N){
        count = N;
        id = new int[N];
        sz = new int[N];
        for(int i = 0;i<N;i++){
            id[i] = i;
            sz[i] =1;
        }
    }
    public int getCount(){
        return count;
    }
    public boolean connected(int p,int q){
        return find(p) == find(q);
    }
    private int find(int p){
        while(p != id[p])
            p = id[p];
        return p;
    }
    public void union(int p,int q){
        int i = find(p);
        int j = find(q);
        if(i == j)
            return;
        if(sz[i] < sz[j]){//将较小的连通分量链接到较大的连通分量中
            id[i] = j;
            sz[j] += sz[i];
        }
        else{
            id[j] = i;
            sz[i] += sz[j];
        }
        count --;
    }
}
复制

总结：由上面的算法优化可以知道，算法优化不是一步到位的，它中间需要一个过程