并查集

概述

并查集定义

并查集(Union-Find Set)，顾名思义，是实现快速合并集合与查询元素所在集合的数据结构。

基本操作

1. 合并两个不相交集合（Union）
2. 判断两个元素是否属于同一个集合（Find）

基于此，可以实现一个并查集的Java接口如下：

public interface UF {
    int getSize();  // 获取元素个数
    boolean find(int p, int q); // 判断两个元素是否属于同一集合
    void union(int p, int q);   // 合并两个不相交的集合
}

实现思路

Quick Find概述

如图，使用一个数组id标识不同元素所属的集合。

则并查集的实现逻辑如下。由于可以直接通过索引得到某元素所属的集合，则Find操作的时间复杂度为O(1)，但Union操作由于要遍历整个数组，因此时间复杂度为O(n)。

public class UnionFind1 implements UF {

    private int[] id;

    public UnionFind1(int size) {
        id = new int[size];
        for(int i=0;i<id.length;i++)
            id[i] = i;
    }

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

    // 获取元素所属集合
    private int getID(int p) {
        if (p < 0 || p >=id.length)
            throw new IllegalArgumentException("p is illegal");
        return id[p];
    }

    // 查看元素p和元素q是否所属同一个集合
    @Override
    public boolean find(int p, int q) {
        return getID(p) == getID(q);
    }

    // 合并元素p和元素q
    @Override
    public void union(int p, int q) {
        int pID = getID(p);
        int qID = getID(q);
        if(pID == qID)
            return;
        for (int i=0;i<id.length;i++) {
            if(id[i] == qID)
                id[i] = pID;
        }
    }
}

Quick Union概述

很显然，之前的Quick Find中查找是否属于同一元素速度很快，而Quick Union则着重于合并的速度。

如图所示，Quick Union的设计思想采用树（森林）进行。每个集合都使用一个根节点进行标识（根节点的父节点为其自身），在具体存储时，也可以使用一个parent数组来标识其父节点的位置。因此：

Find操作只需要找到对应节点的根节点判断是否相等即可；

Union操作只需要将一个元素的根节点指向Union操作的另一元素的根节点即可，具体如图将元素1与元素2进行合并的操作示意

具体实现如下（略去了不关键的几个方法）：这种方法下，find与union操作的时间复杂度都为O(h)，h为树的深度。

public class UnionFind2 implements UF {

    private int[] parent;

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

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

    private int getID(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;
    }

    @Override
    public boolean find(int p, int q) {
        return getID(p) == getID(q);
    }

    @Override
    public void union(int p, int q) {
        int pRoot = getID(p);
        int qRoot = getID(q);

        if(pRoot == qRoot)
            return;

        parent[pRoot] = qRoot;
    }
}

优化

Quick Union的效率与树的深度有关，因此需要尽可能的缩短树的深度，从而提高效率。

思路1：记录每棵树的节点个数

节点个数多的树大概率深度高，因此让节点个数少的集合的根节点指向节点个数大的根节点即可。代码逻辑如下（sz[i]表示以i为根的集合中元素个数）

@Override
public void union(int p, int q) {
    int pRoot = getID(p);
    int qRoot = getID(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];
    }
}

思路2：记录没棵树的深度

思路1的主要漏洞在于节点个数多的树未必深度大，因此可以通过记录树的深度来进行判断，代码逻辑如下（rank[i]表示以i为根的集合的层数）

public void union(int p, int q) {
    int pRoot = getID(p);
    int qRoot = getID(q);

    if(pRoot == qRoot)
        return;

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

思路3：路径压缩（Path Compression）

使用parent[p] = parent[parent[p]]这种逻辑在每次获取根节点时将树的高度缩减。

private int getID(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;
}

使用递归直接将，每个元素直接连接在集合的根节点上

private int getID2(int p) {
    if (p < 0 || p >= parent.length)
        throw new IllegalArgumentException("p is out of bound");
    if(p != parent[p]) {
        parent[p] = getID2(p);
    }
    return parent[p];
}

Donate