Union-Find

Quick Find

数组的每个位置存相应的节点id，相连接的节点的位置存相同的id。
判断是否相连（connected）只需判断两位置的id是否相同。
而将两节点连接起来（union）则需要将第一个节点的id下所有的节点都更改为第二个节点的id。

public class QuickFind{
    private int[] id;
    public QuickFind(int N){
        id = new int[N];
        for(int i = 0;i < N;i++){
            id[i] = i;  
        }
    }

    //判断是否相连
    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){
            return;
        }
        for(int i  = 0;i<id.length;i++){
            if(id[i] == pid){
                id[i] = qid;
            }
        }
    }
}

在上述程序中，查找（connected）的时间复杂度为O(1)，而union和initialize的时间复杂度均为O(N)。

Quick Union

数组的每个位置存的是其父节点；
判断两个节点是否相连（connected）需判断两节点是否有相同的根节点。
将两个节点连接（union）则只需将第一个节点的根节点作为第二个节点根节点的孩子即可。

public class QuickFind{
    private int[] id;
    public QuickFind(int N){
        id = new int[N];
        for(int i = 0;i < N;i++){
            id[i] = i;  
        }
    }

    //找根节点
    public int root(int q){
        while(id[q] != q){
            q = id[q];
        }
        return q; 
    }

    //判断是否相连
    public boolean connected(int p,int q){
        return root(p)==root(q);
    }

    //将两点相连
    public void union(int p,int q){
        id[root(p)] = root(q);
    }
}

由于查找和归并都需要找根节点，因此这里面所有的方法时间复杂度都为O(N)。

Quick-Union Improvements

由于quick union中可能会碰到tall tree，那么寻找其根节点就是一个很耗时的工作。
改进算法中应用了 weighted algorithm，也就是在连接的时候每次将较小的tree连到较大的tree上，避免让较大的tree在某个tree的底部从而使这个tree变得很长。
此时需要另一个数组sz存储每个tree的大小。

public class QuickFind{
    private int[] id;
    private int[] sz;
    public QuickFind(int N){
        id = new int[N];
        sz = new int[N];
        for(int i = 0;i < N;i++){
            id[i] = i;  
            sz[i] = 1;
        }
    }

    //找根节点
    public int root(int q){
        while(id[q] != q){
            q = id[q];
        }
        return q; 
    }

    //判断是否相连
    public boolean connected(int p,int q){
        return root(p)==root(q);
    }

    //将两点相连
    public void union(int p,int q){
        int i = root[p];
        int j = root[q];
        if(i==j){
            return;
        }
        if(sz[i]<sz[j]){
            id[i] =j;
            sz[j]+=sz[i];
        }else{
            idj] = i;
            sz[i]+=sz[j];
        } 
    }
}

拥有N个节点的树的最大深度为logN。因此此方法中connected和union的时间复杂度应为O(logN)

更进一步的改进：path compression

在搜索根节点时会走过路径上的所有点，莫不如将路径上的所有点都直接加到根节点上。为了时间复杂度的效率及代码的简洁性，考虑将路径上的每一个节点加到其祖父节点（grandparent）下。

public int root(int q){
        while(id[q] != q){
            id[q] = id[id[q]];//将该节点加到其祖父节点下
            q = id[q];
        }
        return q; 
    }

http://visualgo.net/ufds 展示的为最后path compression的做法（搜索根节点时将路径上每个结点加到根节点上）。