并查集算法总结

1. 算法简介

并查集是用于寻找图中相连元素的一个工具，它的思想是通过将同一个连通图中的元素都以树的形式进行连接。实际操作就是建立一个 父节点数组，将一条边表示的连接关系更新到父节点数组中的流程为：

1. 分别寻找边两端结点的根结点（就是最顶层的父节点）；
2. 根据两个结点的根结点是否相等进行操作：
   1. 如果两个根结点相等，则说明这两个结点已经在一个连通图中了，添加的这一条边可以在原图中形成一个环；
   2. 如果两个根结点不相等，则说明边的两端的结点原先不在一个连通图中，此时，要一个根结点的父节点设为另一个根结点即可（压缩算法，让秩大的根结点作为父节点）。

具体参考下面代码：

class UnionFind {

    private final int[] parent;
    /**
        * 以 i 为根结点的子树的高度（引入了路径压缩以后该定义并不准确）
        */
    private final int[] rank;

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

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }

        if (rank[rootX] == rank[rootY]) {
            parent[rootX] = rootY;
            // 此时以 rootY 为根结点的树的高度仅加了 1
            rank[rootY]++;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
            // 此时以 rootY 为根结点的树的高度不变
        } else {
            // 同理，此时以 rootX 为根结点的树的高度不变
            parent[rootY] = rootX;
        }
    }

    /**
    *  ! 进行了路径压缩处理。
    *
    * 即：这个 find 可以在寻找根结点的同时，将寻找过程所经过的链路上的所有结点 全部降至秩为1（也就是直接连接到根结点）
    *
    *  例子1：
    *  连接关系：{0,1},{2,3},{1,2}， 则parent 数组为：{1, 3, 3, 3，4}，rank 数组为：{1, 2, 1, 3, 1}
    *  即位号为1的元素深度为2，因为它具有一个子节点为0，位号为1的元素的父节点为3，所以位号为3的元素秩为 3.
    *  这时候，如果添加一个连接关系，修改连接关系为： {0,1},{2,3},{1,2},{4,0}，
    *  在执行 find(0) 的时候，会将 0 的父节点设置为 3， 从而让 parent数组变为 {3, 3, 3, 3, 3}
    *  也就是除3外，秩全部都归为了 1，形象的感觉是将链拉平了。
    *
    *  需要注意的是，本节代码中，并没有做秩的更新处理，也就是结点被拉“平后”，
    *  秩应该都变为1，但是在本节代码中未做相关更新。
    */
    public int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

2. 代码分析

上述代码中，如分析中所介绍，核心的是 union 函数，就是将一条边表示的关系更新到 parent 数组中。

union() 函数需要调用 find() 函数，就是寻找根节点的函数。在上述代码中，在类初始化的时候初始化了 parent 数组，将每个节点的父节点设置为了自己，因此，在 find() 函数中，判断是否找到根节点的判定条件为x != parent[x]，如果不等于，说明还没有找到最终的根节点。

此外，find() 函数还是用递归的方法进行了路径的压缩，具体的过程参考上述代码中的注释部分。

最后，上述代码中还引入了一个 rank 数组，这个数组存放对应节点的在树中位置的深度，在进行树的拼接过程中，需要将深度小的节点接到深度大的节点上，从而优化树的深度，让树尽量平衡。当然，由于使用了路径压缩，这个深度会由于压缩而变化，但上述代码中并没有对此进行更新（似乎更新的意义不大）。