[并查集]并查集的升级路线(四)

路径压缩并查集

并查集在经过了quick-find、quick-union、加权quick-union的演化之后，我们拥有了一个暂时看起来非常不错的算法，就是加权quick-union。经过分析和总结后，加权quick-union的操作可以将树的深度控制在log(n)的级别，相较于单纯的quick-union已然是一个不错的选择，但是进一步优化，可不可以将log(n)提升呢？甚至打到O(1)的时间复杂度？

要想在进一步优化，那么就需要保证并查集中每一颗树的深度都可以在常熟级别内，那么，需要做的事情，就是在树的构建过程中，不断把路径压缩，从而达到减少find操作的深度。

举个例子

image.png

图中所示，这是一颗不平衡的树，从根节点的4到叶子节点的0一共有5层，如果我们将0的父节点不再是指向1，而是指向2，那么树的深度也就可以由5层变为4层，完成了路径压缩。如下图

image.png

那么问题来了，应该在哪一个环节进行这样的改造呢？

还是从代码层面来分析一下

package com.zt;

public class WeightedQuickUnionUnionFind extends UnionFind {

    // 分量权重数组,数组里的值代表当前分量下的分量数量
    private int[] weightArr ;

    public WeightedQuickUnionUnionFind(int n) {

        super(n);
        weightArr = new int[n];
        // 初始化权重数组,初始化是每个分量下的权重都为1
        for (int i = 0; i < weightArr.length; i++) {
            weightArr[i] = 1;
        }
    }

    @Override
    void union(int p, int q) {
        // 找到p的标识
        int pId = find(p);
        // 找到q的标识
        int qId = find(q);

        // 如果两个标识相等,代表已经合并
        if (pId == qId) return;

        // 将权重小的树,合并到权重大的树下
        if (weightArr[pId] < weightArr[qId]) {
            id[pId] = qId;
            weightArr[qId] += weightArr[pId];
        } else {
            id[qId] = pId;
            weightArr[pId] += weightArr[qId];
        }

        // 每次合并操作,会降低一个不同分量组
        count--;
    }

    @Override
    int find(int p) {
        // 沿着标识路径一路寻找,直到找到树的标识
        while (p !=id[p]) p = id[p];
        return p;
    }
}

由代码中可以发现，其实我们在寻找p或者q的标识的时候，默认情况下就需要遍历这棵树的层级，而且，除了遍历以外的事情我们都没有做，这样单纯的遍历，一定程度上浪费了一些性能，那么不妨从这里入手，我们把find方法进行一下改造。

改造的办法也很简单，就是在加权quick-union的find方法中再做一次小的变化

package com.zt;

public class PathCompressionQuickUnionUnionFind extends UnionFind {

    // 分量权重数组,数组里的值代表当前分量下的分量数量
    private int[] weightArr;

    public PathCompressionQuickUnionUnionFind(int n) {

        super(n);
        weightArr = new int[n];
        // 初始化权重数组,初始化是每个分量下的权重都为1
        for (int i = 0; i < weightArr.length; i++) {
            weightArr[i] = 1;
        }
    }

    @Override
    void union(int p, int q) {
        // 找到p的标识
        int pId = find(p);
        // 找到q的标识
        int qId = find(q);

        // 如果两个标识相等,代表已经合并
        if (pId == qId) return;

        // 将权重小的树,合并到权重大的树下
        if (weightArr[pId] < weightArr[qId]) {
            id[pId] = qId;
            weightArr[qId] += weightArr[pId];
        } else {
            id[qId] = pId;
            weightArr[pId] += weightArr[qId];
        }

        // 每次合并操作,会降低一个不同分量组
        count--;
    }

    @Override
    int find(int p) {
        // 沿着标识路径一路寻找,直到找到树的标识
        while (p != id[p]) {
            // 将父节点指向父节点的父节点,完成一次压缩操作
            id[p] = id[id[p]];
            p = id[p];
        }
        return p;
    }
}

样本验证

构造了一个样本数据集，来说明路径压缩的问题

-------------------------------
    0    5    4
    1    9    5
    2    4    7
    3    4    5
    4    5    1
    5    1    0
    6    5    1
    7    6    7
    8    1    2
    9    6    1
   10    7    1
-------------------------------

未压缩路径执行结果

-------------------------------
    0    1    2    3    4    5    6    7    8    9
-------------------------------
    5    5    5    3    5    5    5    6    8    5
-------------------------------

image.png

压缩路径执行结果

-------------------------------
    0    1    2    3    4    5    6    7    8    9
-------------------------------
    5    5    5    3    5    5    5    5    8    5
-------------------------------

image.png

经过进一次的优化后，可以看到并查集中的树的层级又再一次得到了进化，深度由原来的3变为了2。

更进一步

其实通过代码可以发现，我们在路径压缩的过程中，只是简单的把父节点指向了父节点的父节点，但是实际上，我们可以直接将父节点指向根节点，就可以保证每次find操作都是在O(1)时间内

代码如下

    @Override
    int find(int p) {
        if (p == id[p]) return p;
        // 递归直接找到根节点,将分量直接指向根节点,完成彻底的路径压缩.
        id[p] = find(id[p]);
        return id[p];
    }

实际上的代码变动也很简单，只是进行了一次递归，将分量指向根节点。

至此，我们完成了并查集的全部升级路线，实际上，即便是最终的路径压缩方案，也没办法完美的打到O(1)时间复杂度，因为我们仍然还有递归操作，但是这样也可以带来了更高的性能提升。

总结

其实从并查集的升级路线来看，我们每一次的升级改动并不大，只不过是根据实际的问题发生，找到了算法性能瓶颈点，然后一步步分析突破，最后可以得到一个优质的算法，而且，每一步的升级，都进行了样本的验证，通过样本示例可以佐证我们的方案是正确的。

展望

后续会进一步结合实际的应用，将并查集的思想和实际结合起来，能够学会更好的运用这种数据结构。