并查集 - 简书

并查集

等价关系

关系R是描述集合S每对元素（a，b），a R b是真或者假，假如a R b是真的，那么我们说a关联于b。而一个等价关系需要满足以下三个特征：

自反
对称
传递
比如<=就不是等价关系，因为它不满足对称性;电气连接、城市连接显而易见都是等价的。

动态等价关系问题

给定一个定价关系_{，对于任意的a和b判断a是否}b。假如这个关系存储在一个二维的布尔类型的数组中，这样就可以线性的解决，但问题这种关系往往不是显性而是隐性的。
举一个例子，假设一个有5个元素的集合{a₁，a₂，a₃，a₄，a₅}，这样就有25对元素，每一个和另外一个有或者没有关联。当我们知道a₁ ~ a₂，a₃ ~ a₄，a₅ ~ a₁，a₄ ~ a₂，这也意味着所有的组对都是关联的，这个很好推断。
元素a的等价类是包含所有元素S的子集和a有关联的所有元素，等价类是S的一个分区，S中的每一个成员也必然准确的出现在一个等价类中。通过检查a和b是否在同一个等价类中来拍判断a~b。
通常输入开始是只有一个元素的N个集合，代表了刚开始所有的元素是没有关联的。每一个集合有不同的元素，S_i和S_j的交集为空，称为不相交集。
有两个比较显而易见的操作，首先是find，它会返回给定一个元素的等价类，然后是添加关联操作，假如我们要添加关系a~b，我们首先需要看a和b是否已经关联，可以通过finds操作来检查a和b是否有相同的等价类。假如他们没有，我们执行union操作，这个操作合并包含a的等价类和b的等价类到一个等价类中。我们可以通过以下代码来实现

public class DisjSets {
    private int[] s;
    public DisjSets(int numElements) {
        s = new int[numElements];
        for(int i = 0; i < s.length; i++) {
            s[i] = -1;
        }

    }

    public void union(int root1, int root2) {
        s[root2] = root1;
    }

    public int find(int x) {
        if(s[x] < 0) {
            return x;
        } else {
            return find(s[x]);
        }
    }
}

当然以上实现比较随意，就是将第二个树作为第一个树的子树。一个简单的提升是通常让小的树作为大的树的子树，也通常被称为union-by-size。另外一种方法监控每一个子树的深度，尽量使深度越浅越好，只有当两个等价树相交时才会增加深度。我们通常使深度初始位-1，并存储深度的负值。如以下代码所示:

    public void union(int root1, int root2) {
        if(s[root2] < s[root1]) {
            s[root1] = root2;
        } else {
            if(s[root1] == s[root2]) {
                s[root1]--;
            }
            s[root2] = root1;
        }
    }

union/find算法在大多数时候都是可以被接受的，通过上面我们优化了union算法，那么对于find算法比较有名的操作是路径压缩，比如执行find(x),路径压缩就是从x到root节点的每一个节点将他们的父节点改为root节点。代码如下:

    public int find(int x) {
        if(s[x] < 0) {
            return x;
        } else {
            return s[x] = find(s[x]);
        }
    }