并查集及Java实现

并查集及Java实现

概述：
并查集（UnionFindSet）是一种树形数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题，在使用中常常以森林来表示。
常见的 *** 作有合并两个集合、查找某元素属于哪个集合、判断两个元素是否属于同一个集合。

基本 *** 作：
初始化（makeSet）：把每一个元素初始化为一个集合，即将每个元素的父结点初始化为自己

public void makeSet() {
        for (int i = 0; i < this.n; i++) {
            this.parent[i] = i;
            this.rank[i] = 0;
        }
    }

查找（findSet）：查找一个元素所在的集合。在执行查找 *** 作时，要沿着父结点指针一直找下去，直到找到树根为止

public int findSet(int x) {
        if (x == parent[x]) {
            return parent[x];
        }
        return parent[x] = findSet(parent[x]);
    }

合并两个集合（unionSet）：将一个集合的祖先作为另一个集合的祖先。
两种优化策略，

1. 按秩合并，合并的时候将集合的祖先的高度(秩)低的合并到集合的祖先的高度(秩)高的中，这样合并之后树的高度会相对较小

2. 路径压缩，当经过“递推”找到祖先结点后，“回溯”的时候顺便将它的子孙结点都直接指向祖先
   

完整代码如下，

public class UnionFindSet {

    private int n;
    private int[] parent;
    private int[] rank;

    public UnionFindSet(int n) {
        this.n = n;
        this.parent = new int[n];
        this.rank = new int[n];
    }

    public void makeSet() {
        for (int i = 0; i < this.n; i++) {
            this.parent[i] = i;
            this.rank[i] = 0;
        }
    }

    public int findSet(int x) {
        if (x == parent[x]) {
            return parent[x];
        }
        return parent[x] = findSet(parent[x]);
    }

    public void unionSet(int x, int y) {
        x = findSet(x);
        y = findSet(y);
        if (x == y) {
            return;
        }
        if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }

}