并查集(Union-find Set)及java实现

并查集

并查集处理集合之间的关系，即 'union'合并和 'find'查找。
在这种数据类型中，N个不同元素被分成若干个组，每组是一个集合，这种集合叫做分离集合。
并查集支持查找一个元素所属的集合和两个元素分别所属的集合的合并。

并查集支持的操作
MAKE(X): 建立一个仅有成员X的新集合。
UNION(X,Y)：将包含X和Y的动态集合合并为一个新集合S，此后该二元素处于同一集合。
FIND(X)：返回一个包含X的集合。
注意：并查集只能进行合并操作，不能进行分割操作。

并查集实现原理
并查集是使用树结构实现的：
1.初始化：准备N个节点来表示N个元素，最开始没有边。
2.合并：从一个组的根向另一个组的根连边，这样两棵树就变为了一棵树，也就把两个组合并为一个组了。
3.查询：查询两个节点是否在同一个组，只需要查询他们是否具有相同的根。

注意：
（1）为避免树的退化，对于每棵树，记录其高度rank。
（2）如果合并时两棵树高度不同，那么从rank小的向rank大的连边。
（3）为了简化后续查询，在查询某个节点时，一旦向上走到了一次根节点，就把这个节点到父亲的边改为直接连向根。不仅指查询的节点，也包括查询过程中经过的节点。使用这种简化的方法时，即使树的高度发生了改变，我们也不修改rank值。

并查集的复杂度
对N个元素并查集进行的一次操作的复杂度是O(α(N))，α(N)是阿克曼函数的反函数。这个复杂度是比O(LogN)还要快的。

java实现

import java.util.HashMap;
import java.util.List;
import java.util.Arrays;

public class UnionFind<E> {
    private HashMap<E,E> parent = null; // 一棵树表示一个集合
    private HashMap<E,Integer> rank = null;  // 记录树高度信息，避免树退化
    private int count = 0; // 集合数

    public UnionFind(List<E> list) {
        parent = new HashMap<>();
        rank = new HashMap<>();
        count = list.size();
        for ( E e : list ) {
            parent.put(e, e);
            rank.put(e, 0);
        }
    }

    public HashMap<E, E> parent() {
        return parent;
    }

    public HashMap<E, Integer> rank() {
        return rank;
    }

    public int numSubsets() {
        return count;
    }

    // 查找元素
    public E find(E e) {
        E pe = parent.get(e);
        while ( ! pe.equals(e) ) {
            parent.put(e, parent.get(pe)); // 将该节点到父亲的边更新为直接连向根，方便后续查询
            e = parent.get(e);
            pe = parent.get(e);
        }
        return e;
    }

  // 合并两个节点所在的集合
    public void union(E e1, E e2) {
        E root1 = find(e1), root2 = find(e2);
        // 若两个节点在同一个节点(根相同)则不合并
        if ( root1.equals(root2) ) {
            return;
        }
        // 按照树高rank，将低的连到高的， 树高不变
        if ( rank.get(root1) < rank.get(root2) ) {
            parent.put(root1, root2);
        }
        else if ( rank.get(root1) > rank.get(root2) ) {
            parent.put(root2, root1);
        }
        // 若两棵树高度相同，连后高度+1
        else {
            parent.put(root2, root1);
            rank.put(root1, 1 + rank.get(root1));
        }
        count--; // 连后树数量-1
    }

    public static void main(String[] args) {
        System.out.println("初始化: ");
        String[] labels = {"a", "b", "c", "d", "e", "f", "g", "h"};
        UnionFind<String> uf = new UnionFind<>(Arrays.asList(labels));
        System.out.println("uf.parent() = " + uf.parent());
        System.out.println("uf.rank() = " + uf.rank());
        System.out.println("count = " + uf.numSubsets());

        System.out.println("join b & e, c & d 之后: ");
        uf.union("b", "e");
        uf.union("c", "d");
        System.out.println("uf.parent() = " + uf.parent());
        System.out.println("uf.rank() = " + uf.rank());
        System.out.println("count = " + uf.numSubsets());

        System.out.println("join e & h, a & g, h & c 之后: ");
        uf.union("e", "h");
        uf.union("a", "g");
        uf.union("h", "c");
        System.out.println("uf.parent() = " + uf.parent());
        System.out.println("uf.rank() = " + uf.rank());
        System.out.println("count = " + uf.numSubsets());

        System.out.println("join f & g 之后:");
        uf.union("f", "g");
        System.out.println("uf.parent() = " + uf.parent());
        System.out.println("uf.rank() = " + uf.rank());
        System.out.println("count = " + uf.numSubsets());
    }
}

输出结果为：

初始化: 
uf.parent() = {a=a, b=b, c=c, d=d, e=e, f=f, g=g, h=h}
uf.rank() = {a=0, b=0, c=0, d=0, e=0, f=0, g=0, h=0}
count = 8
join b & e, c & d 之后: 
uf.parent() = {a=a, b=b, c=c, d=c, e=b, f=f, g=g, h=h}
uf.rank() = {a=0, b=1, c=1, d=0, e=0, f=0, g=0, h=0}
count = 6
join e & h, a & g, h & c 之后: 
uf.parent() = {a=a, b=b, c=b, d=c, e=b, f=f, g=a, h=b}
uf.rank() = {a=1, b=2, c=1, d=0, e=0, f=0, g=0, h=0}
count = 3
join f & g 之后:
uf.parent() = {a=a, b=b, c=b, d=c, e=b, f=a, g=a, h=b}
uf.rank() = {a=1, b=2, c=1, d=0, e=0, f=0, g=0, h=0}
count = 2