并查集

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

• 合并（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;    }