Union-Find算法

• Union-Find算法
  • 简介
  • 原理
  • 改进
  • 应用
  • References

Union-Find算法

1.简介

Union-Find算法又称并查集算法，是一种作用于并查集数据结构的算法。包含两个主要的操作：
- Find 用于查找某个元素属于哪个集合，可以用来确定两个元素是否在同一个集合中；
- Union 用于合并两个不同的集合；

2.原理

并查集数据结构是一种树形结构，树形结构对于有规律的数据组织方式，进行修改和查找十分高效。
具体结构如下图一所示：

图一

图二

图一展示了并查集的树形结构，每一棵独立的树都代表一个独立的集合，在同一棵树下的所有节点自然就是属于同一个集合。
图二表示了并查集的存储结构，并查集数据结构采用数据对树进行存储，元素i的值id[i]存储的是其在树形结构上对应的父节点的标号，而根节点元素root的值id[root]是本身的标号，即root = id[root];

有了上述的树形结构和数据的组织形式后，一些基本的操作就变得简单了。
- root(x) 返回元素x所在树的根节点，从当前元素x的父节点id[i]不断的向上递推求父节点，直到id[i] == i成立。
- connected(x, y)判断x和y元素是否是连通的（直接或间接）,只需要判断两个节点是否有相同的根节点（即是否在同一棵树中）；
- count(x) 获取元素x所在集合（树）的元素（节点）的个数,以根节点来分别统计每棵树的节点的数目；
- find(x) 返回元素x的根节点
- union(x,y) 将元素x和y连通，将x所在的树的拼接到y所在树种，（反之亦可）即将x的根节点父节点设置为y的根节点。

上述的操作基本上覆盖了并查集数据结构以及算法中的大部分操作，由此可以写出一个基本的并查集算法雏形：

class UnionFind {

    private int[] id;

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

    public boolean connected(int i, int j) {
        return root(i) == root(j);
    }

    private int root(int i) {
        int root;
        while ((root = id[i]) != i)
            i = id[i];  
        return root;
    }

    public int find(int i) {
        return root(i);
    }

    public void union(int i, int j) {
        int rootI, rootJ;
        if ((rootI = root(i)) == (rootJ = root(j)))
            return;
     id[rootI] = rootJ;//将i节点所在树移接到j节点所在树
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        Map<Integer, List<Integer>> group = new HashMap<>();
        for (int i = 0 ; i < this.id.length; i++) {
            int root = root(i);
            if (group.get(root) == null) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(i);
                group.put(root, tmp);
            } else 
                group.get(root).add(i);
        }
        return group.toString();
    }
}

3.改进

对上述Union-Find的两个主要操作find和union的时间复杂度进行分析易得出
- union(i,j) — O(1)
- find(i) — O(h) 其中h是节点i所在树的高度

由于在进行对两个节点进行union操作的时候，我们总是不加选择的将节点i所在的树拼接到节点j所在的树下，这样可能会导致某一棵树特别的瘦高，即其h很大，几乎可以接近于n，从而可能导致find操作可能需要遍历整个集合。

图三

由于这个原因，我们需要不断的调整树，使其变得稍微矮胖一些，如图四。

图四

为了将树摊平，存在两个改进的地方：
- 带权的union操作 即在进行union操作的时候，可以先判断节点所在树的大小，将size小的树接到size大的树；
- 路径压缩 即在进行find操作的时候，在找到根节点后，循环将该路径下的所有节点都拼接到根节点下，如图五所示；

图五

图六

改进后union-find

class UnionFind {

    private Map<Integer, Integer> memSize;
    private int[] id;

    public UnionFind(int size) {
        memSize = new HashMap<>();
        id = new int[size];
        for (int i = 0; i < size; i++) {
            id[i] = i;
            memSize.put(i, 1);
        }
    }

    public boolean connected(int i, int j) {
        return root(i) == root(j);
    }

    private int root(int i) {
        int root;
        while ((root = id[i]) != i) {
            //优化二：路径压缩，将当前非root节点i 拼接到爷节点下面，将爷节点作为自己的父节点
            //这样为后续查找节点i的root节点压缩路径深度，节约了时间。
            id[i] = id[id[i]];
            i = id[i];  
        }

    //或者另一种路径压缩方式
    /* while (id[i] != i) {
      id[i] = root;
      i = id[i];
    } */

        return root;
    }

    public int find(int i) {
        return root(i);
    }

    public void union(int i, int j) {
        int rootI, rootJ;
        if ((rootI = root(i)) == ( rootJ = root(j)))
            return;
        int iSize, jSize;
        //优化一：带权union, 小树接大树，避免新树过高；
        if ((iSize = memSize.get(rootI)) > (jSize = memSize.get(rootJ))) {
            id[rootJ] = rootI;
            memSize.put(rootI, iSize + jSize);
        } else {
            id[rootI] = rootJ;
            memSize.put(rootJ, iSize + jSize);
        }
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        Map<Integer, List<Integer>> group = new HashMap<>();
        for (int i = 0 ; i < this.id.length; i++) {
            int root = root(i);
            if (group.get(root) == null) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(i);
                group.put(root, tmp);
            } else 
                group.get(root).add(i);
        }
        return group.toString();
    }
}

4.应用

• Percolation.
• Games (Go, Hex).
• Dynamic connectivity.
• Least common ancestor.
• Equivalence of finite state automata.
• Hoshen-Kopelman algorithm in physics.
• Hinley-Milner polymorphic type inference.
• Kruskal’s minimum spanning tree algorithm.
• Compiling equivalence statements in Fortran.
• Morphological attribute openings and closings.
• Matlab’s bwlabel() function in image processing.

5.References

[1] Algorithms - Robert Sedgewick, Kevin Wayne