并查集

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

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