并查集

并查集被认为是最简洁而优雅的数据结构之一，次要用于解决一些元素分组的问题。它治理一系列不相交的汇合，并反对两种操作：

• 合并（Union）：把两个不相交的汇合合并为一个汇合。
• 查问（Find）：查问两个元素是否在同一个汇合中。

Quick Find

第一个版本的并查集

public interface UnionFind {
        boolean isConnected(int p,int q);
        void unionElements(int p ,int q);
        int getSize();
}

public class UnionFind1 implements UnionFind {
        private int[] id;
        public UnionFind1(int size) {
            id = new int[size];
            for (int i = 0; i < id.length; i++) {
                id[i] = i;
            }
        }
        //查看元素p和元素q是否属于一个汇合
        @Override
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
        //合并元素p和元素q所属的汇合
        @Override
        public void unionElements(int p, int q) {
            int pID = find(p);
            int qID = find(q);
            if (pID == qID) {
                return;
            }
            for (int i = 0; i < id.length; i++) {
                if (id[i] == pID) {
                    id[i] = qID;
                }
            }
        }
        @Override
        public int getSize() {
            return id.length;
        }
        // 查找元素p所对应的汇合编号
        private int find(int p) {
            if (p < 0 || p >= id.length) {
                throw new IllegalArgumentException("p is out of bound.");
            }
            return id[p];
        }
}

Quick Union

咱们能够将每一个元素都看作是一个节点。

如果节点3想要连贯节点2，那就是节点3去连贯节点2，而2又指向本人

如果节点1想要连贯节点3也是须要连贯节点2即可。如果另一个节点的7想要连贯2也是须要以后节点的根节点去连贯2即可。

一开始的时候应用数组示意，每一个节点都是根节点和其余节点无关联。

如果咱们想union 4，3 节点，咱们只须要让4指向3即可。

如果想union3，8其实也非常简单，只须要用3指向8的节点

如果想union9，4其实并不是指向4这个节点，而是指向4的根节点的8。

public class UnionFind2 implements UnionFind{

    private int[] parent;


    public UnionFind2(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    //查看元素p和元素q是否属于一个汇合
    // O(h)复杂度，h为树的高度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并元素p和元素q所属的汇合
    // O(h)复杂度，h为树的高度
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        parent[pRoot] = qRoot;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    //查找过程，查找元素p所对应的汇合编号
    // O(h)复杂度，h为树的高度
    private int find(int p){
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while(p != parent[p]){
            p = parent[p];
        }
        return p;
    }
}

基于Size的优化

如果咱们union 0，1 而后 union 0，2 而后 union 0，3这样的话就会产生肯定的问题，因为咱们没有对合并的元素的树没有做判断，所以会导致咱们一直减少树的高度，从而成链表的构造。

如果咱们的树是这样子的。

咱们想union 4，9的话，咱们的树就会变成这个样子。深度就达到了4。

但其实咱们能够让9来指向4的根节点也就是8。这样咱们的深度就只有3。

public class UnionFind3 implements UnionFind{

    private int[] parent;
    //sz[i] 示意以i为根的汇合中元素个数
    private int[] sz;


    public UnionFind3(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    //查看元素p和元素q是否属于一个汇合
    // O(h)复杂度，h为树的高度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并元素p和元素q所属的汇合
    // O(h)复杂度，h为树的高度
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if(sz[pRoot] < sz[qRoot]){
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else{
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }

    }

    @Override
    public int getSize() {
        return parent.length;
    }

    //查找过程，查找元素p所对应的汇合编号
    // O(h)复杂度，h为树的高度
    private int find(int p){
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while(p != parent[p]){
            p = parent[p];
        }
        return p;
    }
}

基于Rank的优化

假如当初有这样一棵树，咱们进行union4，2依据size优化咱们会把8来指向7。当初深度就变为了4。

然而这样子的话，本来的高度是2一下就变为了4，为了优化其实咱们能够将7来指向8。深度就变为了3。咱们须要将深度低的指向深度高的树

public class UnionFind4 implements UnionFind{

    private int[] parent;
    //rank[i] 示意以i为根的汇合中树的层数
    private int[] rank;


    public UnionFind4(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    //查看元素p和元素q是否属于一个汇合
    // O(h)复杂度，h为树的高度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并元素p和元素q所属的汇合
    // O(h)复杂度，h为树的高度
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //依据两个元素所在树的rank不同判断合并方向
        //将rank低的汇合合并到rank高的汇合上
        if(rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if(rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }else{
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }

    }

    @Override
    public int getSize() {
        return parent.length;
    }

    //查找过程，查找元素p所对应的汇合编号
    // O(h)复杂度，h为树的高度
    private int find(int p){
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while(p != parent[p]){
            p = parent[p];
        }
        return p;
    }
}

门路压缩

下图中三种树的操作其实都是一样的，然而右边的深度达到了5，而两头可只有2。咱们应该如何进行门路压缩？

这样的一棵树构造下，如果咱们进行上面操作

parent[p] = parent[parent[p]];

咱们让4节点来指向父节点的父节点，也就变成了上面这样。

而后咱们再让4的父节点执行同样操作就会变成这样。

 //查找过程，查找元素p所对应的汇合编号
    // O(h)复杂度，h为树的高度
    private int find(int p){
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while(p != parent[p]){
            //门路压缩
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }