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

并查集是为了解决连通性问题，首先现将并查集模型定义出来。

首先并查集中存储的是是分量，不通分量可能存在连通关系，定义一个属性用来描述一个并查集中属于不通标识的分量个数，把并查集看做一个森林，这个count就是森林中树的数量。

并查集抽象父类定义

首先明确并查集中需要做的事情，并查集本省核心的方法就是两个，合并和查找，但是在此之上，我们需要将分量存储，以及连通的判断，所以经过分析，我们需要进行如下步骤。

• 定义并查集分量集合，用数组存储，下标代表分量，对应值代表分量所在树的标识
• 定义并查集森林中树的个数，每进行一次合并操作，树的个数减一。
• 定义并查集构造方法。
• 定义并查集中不同分量的连通性判断方法
• 定义并查集的合并操作
• 定义并查集的查找操作

package com.zt;

abstract public class UnionFind {

    // 存储连分量
    protected int[] id;
    // 当前并查集不同的连通分量总数
    protected int count;

    /** * 连通量构造方法 * * @param n */
    public UnionFind(int n) {
        // 初始化时,没个分量互不连通
        this.count = n;
        // 初始化一个容纳全量分量的数组
        this.id = new int[n];
        for (int i = 0; i < n; i++) {
            // 没个分量初始值指向自身
            id[i] = i;
        }

    }

    /** * 判断两个分量是否连通 * * @param p * @param q * @return */
    boolean connect(int p, int q) {
        // 如果两个分量的标识相等,代表两个分量连通
        return find(p) == find(q);
    }

    /** * 链接两个分量 * * @param p * @param q */
    abstract void union(int p, int q);

    /** * 查找分量的标识 * * @param p * @return */
    abstract int find(int p);

}

quick-find

quick-find是并查集的最初阶解决方案，从名字中可以看出，该算法的目的是要快速找到分量的标识，将查找复杂度定义在O(1)时间复杂度内，每次查找分量标识的时间控制在一次之内。

但是与此同时，union的操作会变得相对复杂很多，为了维护一级层级关系，最差的情况下，每次合并操作都需要改变当前合并的树的标识，那么该树下所有的分量全部都要改变标识。

具体实现步骤

• 定义一个QuickFindUnionFind子类继承UnionFind
• 实现查找方法。
• 实现合并方法。

package com.zt;

/** * @author tian * @date 2021年2月11日 下午3:30:17 * quick-find * 1 保证O(1)时间内找到分量标识 * 2 合并分量时,将分量q及q所在的连通分两组中的所有分量的标识指向与p一致 * * 优点:查找时间O(1) * 缺点 */
public class QuickFindUnionFind extends UnionFind {
    /** * 连通量构造方法 * * @param n */
    public QuickFindUnionFind(int n) {
        super(n);
    }

    @Override
    void union(int p, int q) {

        // 找到p的标识
        int pId = find(p);
        // 找到q的标识
        int qId = find(q);

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

        // 如果不相等,将分量q及q所在的连通分两组中的所有分量的标识指向与p一致
        for (int i = 0; i < id.length; i++) {
            if(id[i] == qId) id[i] = pId;
        }
        // 每次合并操作,会降低一个不同分量组
        count--;
    }

    @Override
    int find(int p) {
        return id[p];
    }
}