数据结构学习笔记 - 12 并查集

介绍

已知两个元素，如何快速判断两个元素是否属于同一个集合？已知两个集合，如何将两个集合合并为同一个集合？并查集就是解决这两个问题的数据结构。

并查集可以非常快判断网络中节点间的连接状态。

并查集是特殊的树结构，它是又孩子指向父亲。

注意并查集只关注两个点的连接问题，而不关注两个点的路径问题（路径问题显然比只关注连接要更复杂）。

并查集也不考虑添加和删除元素，只考虑当下的元素进行并或者查的操作。对于一组数据，并查集主要支持两个动作：

• unionElements(p, q)，即将 p 和 q 两个元素所属的集合合并；
• isConnected(p, q)，判断 p 和 q 两个元素是否属于同一个集合。

接口

并查集接口

public interface UF {

    int getSize();
    boolean isConnected(int p, int q);
    void unionElements(int p, int q);
}

Quick Find

这种实现方式只是在查询上比较快速，在合并操作上并不高效，并不是并查集的最终实现。

/**
 * 我们可以将数据按照如下方式存储，每个元素对应一个 id，id 相同即代表元素属于同一个集合。
 * 
 *     0 1 2 3 4 5 6 7 8 9
 * id  0 1 0 1 0 1 0 1 0 1
 * 
 * 表示 0 2 4 6 8 在一个集合中，1 3 5 7 9 在另一个集合中。
 * 
 * 此时，查找一个元素属于哪个集合就会非常快，只需要 O(1) 的复杂度。
 * 
 *     操作                复杂度
 * isConnected(p, q)       O(1)
 * unionElements(p, q)     O(n)
*/

public class UnionFind implements UF {

    private int[] id; // 这个并查集本质就是一个数组。

    public UnionFind(int size) {
        id = new int[size];

        // 初始化时，并没有合并任何元素。
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    /**
     * 并查集中元素的个数。
     */
    @Override
    public int getSize() {
        return id.length;
    }

    /**
     * 查找元素 p 所对应的集合编号。
     * 复杂度：O(1)
     */
    private int find(int p) {
        if (p < 0 || p >= id.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }

        return id[p];
    }

    /**
     * 查找元素 p 和元素 q 是否属于同一个集合。
     * 复杂度：O(1)
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 合并元素 p 和元素 q 所属的集合。
     * 复杂度：O(n)
     */
    @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;
            }
        }
    }
}

Quick Union

带路径压缩优化的 Quick Union 并查集实现。

/**
 * Quick Union 是并查集的一种更高效的实现。
 * 它将每一个元素都看作是一个节点。
 * 
 *        0 1 2 3 4 5 6 7 8 9
 * parent 1 1 1 8 3 0 5 1 8 8
 * 
 * 上面的内容可以用下面两个树来表示，分别表示两个集合；下面两棵树都是由孩子指向父亲的，根节点指向自己。
 * 
 *         1           8
 *       / | \         | \
 *      0  2  7        3  9
 *      |              |
 *      5              4
 *      |
 *      6
 *
 *    操作                复杂度
 * isConnected(p, q)       O(h)
 * unionElements(p, q)     O(h)
 *
 * 如果加上路径压缩优化后的并查集，上述复杂度可以表示为 O(log*n)，注意 * 可以称为「星」，它不是乘号，这是一个比 O(logn) 更快的更接近的 O(1) 级别的复杂度。
*/

public class UnionFind implements UF {

    // parent[i] 表示第 i 个元素指向的父节点
    private int[] parent;
    // rank[i] 表示以 i 为根的集合所表示的层数
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];

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

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

    // 复杂度为 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;
    }

    // 复杂度为 O(h)，其中 h 为树的高度。
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(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 (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        } else if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = pRoot;
        } else {
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }
}