并查集 Union Find

对于一组数据，主要支持两个动作：

·union(p,q)
·find(p)

用来回答一个问题

·isConnected(p,q)

一、Quick Find

并查集的基本数据表示

0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 1 1 1 1 1

Find

id 0 1 2 3 4 5 6 7 8 9

0 1 0 1 0 1 0 1 0 1

Quick Find 下的 Find 时间复杂度O(1)

Quick Find 下的 Union 时间复杂度O(n)

Quick Find代码实现：

public class UnionFind {

    private int[] id;
    private int count;

    public UnionFind(int n){
        count = n;
        id = new int[n];
        for(int i = 0; i < n; i++){
            id[i] = i;
        }
    }

    public int find(int p) throws Exception {
        if(p < 0 || p >= count)
            throw new Exception("p非法");
        return id[p];
    }

    public boolean isConnected(int p, int q) throws Exception {
        return find(p) == find(q);
    }

    public void unionElements( int p , int q ) throws Exception {
        int pID = find(p);
        int qID = find(q);

        if( pID == qID ){
            return;
        }
        for( int i = 0; i < count ; i ++ ){
            if ( id[i] == pID )
                id[i] = qID;
        }
    }

	//测试
    public static void testUF1(int n) throws Exception {
        Random random = new Random();
        UnionFind uf = new UnionFind(n);
        long startTime = System.currentTimeMillis();
        for( int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.unionElements(a,b);
        }
        for(int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.isConnected(a,b);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("UF1, " + 2 * n + "ops," + (endTime - startTime) / 1000.0);

    }

    public static void main(String[] args) throws Exception {
        int n = 100000;
        testUF1(n);
    }

}

测试结果：

n = 10000

UF1, 20000ops,0.058

n = 100000

UF1, 200000ops,5.083

二、Quick Union

并查集的另外一种实现思路 -- 将每一个元素，看作是一个节点

Quick Union下的数据表示

0 1 2 3 4 5 6 7 8 9

parent 0 1 2 3 4 5 6 7 8 9

Quick Union代码实现：

public class UnionFind2 {

    private int[] parent;
    private int count;

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

    public int find(int p) throws Exception {
        if(p < 0 || p >= count)
            throw new Exception("p非法");
        while( p != parent[p])
            p = parent[p];
        return p;
    }

    public boolean isConnected(int p , int q ) throws Exception {
        return find(p) == find(q);
    }

    public void unionElements(int p , int q ) throws Exception {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        parent[pRoot] = qRoot;
    }

    public static void testUF2(int n) throws Exception {
        Random random = new Random();
        UnionFind2 uf = new UnionFind2(n);
        long startTime = System.currentTimeMillis();
        for( int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.unionElements(a,b);
        }
        for(int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.isConnected(a,b);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("UF2, " + 2 * n + "ops," + (endTime - startTime) / 1000.0);

    }

    public static void main(String[] args) throws Exception {
        int n = 10000;
        UnionFind.testUF1(n);
        testUF2(n);
    }

}

测试结果：

n = 10000

UF1, 20000ops,0.062
UF2, 20000ops,0.031

n = 100000

UF1, 200000ops,4.726
UF2, 200000ops,10.346

2.1 基于Size的优化：

给每一个根节点维护一个size大小，表示这颗树的大小。只需要在合并的时候把size小的合并到size大的树上，即把size小的根节点的父节点赋值为size大的根节点，其它不需要改变。

代码实现：

public class UnionFind3 {

    private int[] parent;
    private int[] size; //size[i]表示以i为根的集合中元素个数
    private int count;

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

    public int find(int p) throws Exception {
        if(p < 0 || p >= count)
            throw new Exception("p非法");
        while( p != parent[p])
            p = parent[p];
        return p;
    }

    public boolean isConnected(int p , int q ) throws Exception {
        return find(p) == find(q);
    }

    public void unionElements(int p , int q ) throws Exception {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if (size[pRoot] < size[qRoot]) {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }else{
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        }
    }

    public static void testUF3(int n) throws Exception {
        Random random = new Random();
        UnionFind3 uf = new UnionFind3(n);
        long startTime = System.currentTimeMillis();
        for( int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.unionElements(a,b);
        }
        for(int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.isConnected(a,b);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("UF3, " + 2 * n + "ops," + (endTime - startTime) / 1000.0);

    }

    public static void main(String[] args) throws Exception {
        int n = 10000;
        UnionFind.testUF1(n);
        UnionFind2.testUF2(n);
        testUF3(n);
    }

}

测试结果：

n = 10000

UF1, 20000ops,0.059
UF2, 20000ops,0.036
UF3, 20000ops,0.003

n = 100000

UF1, 200000ops,4.666
UF2, 200000ops,10.193
UF3, 200000ops,0.019

2.2 基于Rank的优化：

基于Rank的优化，rank[i]表示根节点为i的树的高度。

把rank值小的根节点的父节点赋值为rank值大的根节点，如果两个rank值相同，则选择任意一个节点的根节点赋值为另一个根节点的值，并把另一个节点的rank值加1。

public class UnionFind4 {

    private int[] parent;
    private int[] rank; //rank[i]表示以i为根的集合所表示的树的层数
    private int count;

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

    public int find(int p) throws Exception {
        if(p < 0 || p >= count)
            throw new Exception("p非法");
        while( p != parent[p])
            p = parent[p];
        return p;
    }

    public boolean isConnected(int p , int q ) throws Exception {
        return find(p) == find(q);
    }

    public void unionElements(int p , int q ) throws Exception {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }else { //rank[pRoot] == rank[qRoot]
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }

    public static void testUF4(int n) throws Exception {
        Random random = new Random();
        UnionFind4 uf = new UnionFind4(n);
        long startTime = System.currentTimeMillis();
        for( int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.unionElements(a,b);
        }
        for(int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.isConnected(a,b);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("UF4, " + 2 * n + "ops," + (endTime - startTime) / 1000.0);

    }

    public static void main(String[] args) throws Exception {
        int n = 10000;
        UnionFind.testUF1(n);
        UnionFind2.testUF2(n);
        UnionFind3.testUF3(n);
        testUF4(n);
    }

}

测试结果：

n = 10000

UF1, 20000ops,0.066
UF2, 20000ops,0.033
UF3, 20000ops,0.005
UF4, 20000ops,0.005

n = 100000

UF1, 200000ops,4.865
UF2, 200000ops,10.325
UF3, 200000ops,0.015
UF4, 200000ops,0.014

2.3 路径压缩

前面两种优化方法，优化的地方都集中在union这个操作上。但实际上，在find的这个操作过程中，其实我们也是可以优化的。 在find的过程中，从底向上，如果没有找到根的话，就想办法把这些节点再向上挪一挪，那么这个过程就叫做路径压缩。

2.3.1 方法1

代码实现：

private int[] parent;
    private int[] rank; //rank[i]表示以i为根的集合所表示的树的层数
    private int count;

    public UnionFind5(int n){
        count = n;
        parent = new int[n];
        rank = new int[n];
        for( int i = 0; i < n; i++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int p) throws Exception {
        if(p < 0 || p >= count)
            throw new Exception("p非法");
        while( p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public boolean isConnected(int p , int q ) throws Exception {
        return find(p) == find(q);
    }

    public void unionElements(int p , int q ) throws Exception {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }else { //rank[pRoot] == rank[qRoot]
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }

    public static void testUF5(int n) throws Exception {
        Random random = new Random();
        UnionFind5 uf = new UnionFind5(n);
        long startTime = System.currentTimeMillis();
        for( int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.unionElements(a,b);
        }
        for(int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.isConnected(a,b);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("UF5, " + 2 * n + "ops," + (endTime - startTime) / 1000.0);

    }

    public static void main(String[] args) throws Exception {
        int n = 10000;
        UnionFind.testUF1(n);
        UnionFind2.testUF2(n);
        UnionFind3.testUF3(n);
        UnionFind4.testUF4(n);
        testUF5(n);
    }

测试结果：

n = 10000

UF1, 20000ops,0.079
UF2, 20000ops,0.043
UF3, 20000ops,0.003
UF4, 20000ops,0.004
UF5, 20000ops,0.003

n = 100000

UF1, 200000ops,4.73
UF2, 200000ops,10.115
UF3, 200000ops,0.016
UF4, 200000ops,0.015
UF5, 200000ops,0.013

2.3.2 方法2

代码实现：

public class UnionFind5 {

    private int[] parent;
    private int[] rank; //rank[i]表示以i为根的集合所表示的树的层数
    private int count;

    public UnionFind5(int n){
        count = n;
        parent = new int[n];
        rank = new int[n];
        for( int i = 0; i < n; i++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int p) throws Exception {
        if(p < 0 || p >= count)
            throw new Exception("p非法");
        /*while( p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;*/
        if( p != parent[p]){
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }

    public boolean isConnected(int p , int q ) throws Exception {
        return find(p) == find(q);
    }

    public void unionElements(int p , int q ) throws Exception {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }else { //rank[pRoot] == rank[qRoot]
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }

    public static void testUF5(int n) throws Exception {
        Random random = new Random();
        UnionFind5 uf = new UnionFind5(n);
        long startTime = System.currentTimeMillis();
        for( int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.unionElements(a,b);
        }
        for(int i = 0 ; i < n ; i ++ ){
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            uf.isConnected(a,b);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("UF5, " + 2 * n + "ops," + (endTime - startTime) / 1000.0);

    }

    public static void main(String[] args) throws Exception {
        int n = 100000;
        UnionFind.testUF1(n);
        UnionFind2.testUF2(n);
        UnionFind3.testUF3(n);
        UnionFind4.testUF4(n);
        testUF5(n);
    }

}

测试结果：

n = 10000

UF1, 20000ops,0.067
UF2, 20000ops,0.04
UF3, 20000ops,0.004
UF4, 20000ops,0.004
UF5, 20000ops,0.003

n = 100000

UF1, 200000ops,4.723
UF2, 200000ops,10.439
UF3, 200000ops,0.014
UF4, 200000ops,0.014
UF5, 200000ops,0.013