数据结构笔记总结（10.2）Quick Find

并查集的基本数据表示

在并查集内部我们可以直接给每个数据做一个编号，这里0到9就表示10个不同的数据

当然这是一种抽象的表示，10个编号可能是10个人或10辆车，但在并查集内部我们只存0到9这10个编号，它表示10个具体的元素。

对于每一个元素并查集存储的是一个我们可以称之为叫做它所属于的集合的ID，比如编号为0到4这五个数据它们所对应的这个ID为0，编号为5到9的这五个数据它们所对应的ID为1，不同的ID值可以理解为不同的集合所对应的编号，换句话说，图中并查集中分成两个集合，其中0到4这五个元素在一个集合中，5到9这五个元素再另一个集合中。

同理，如果并查集是这样，就意味着0、2、4、6、8这五个元素为同一个集合，剩下的为另一个集合。这样我们就很容易回答连接问题了，0和2这两个元素是相连接的，因为它们对应的ID相同。

对于我们使用ID这样一个数组来存储数据是很容易回答isConnected这个问题的，只需要直接来看p和q对应的ID值是否一样就好了。我们将我们查询p或者q这些元素每个元素所对应的集合的ID是谁这个过程抽象成一个函数find，对于刚才描述的使用ID来存储每个数据所属的集合是谁的时候，只需要看find(p)是否等于find(q)

当我们使用这种方式来操作的时候，复杂度为O(1)。这种方式是非常快速的，所以这种并查集方式通常也称作Quick Find。

实现Quick Find查询操作

// 我们的第一版Union-Find
public class UnionFind1 implements UF {

    private int[] id;    // 我们的第一版Union-Find本质就是一个数组
    private int size;   // 数据个数

    public UnionFind1(int size) {

        id = new int[size];
        this.size = size;

        // 初始化, 每一个id[i]指向自己, 没有合并的元素
        for (int i = 0; i < size; i++)
            id[i] = i;
    }

    @Override
    public int getSize(){
        return size;
    }

    // 查找过程, 查找元素p所对应的集合编号
    // O(1)复杂度
    private int find(int p) {
        if(p < 0 && p >= size)
            throw new IllegalArgumentException("p is out of bound.");

        return id[p];
    }

    // 查看元素p和元素q是否所属一个集合
    // O(1)复杂度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(n) 复杂度
    @Override
    public void unionElements(int p, int q) {

        int pID = find(p);
        int qID = find(q);

        if (pID == qID)
            return;

        // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
        for (int i = 0; i < size; i++)
            if (id[i] == pID)
                id[i] = qID;
    }
}

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]