• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(10.3)Quick Union

极客笔记 Geekerstar 11个月前 (05-20) 469次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

Quick Union

上一节我们实现了并查集的一种思路,使用数组进行模拟得到一种结果,叫做Quick Find,对于查找这种操作是非常快的。

标准情况下并查集的实现是通过Quick Union这种实现思路。

实现思路

将每一个元素看做是一个节点,节点之间相连接形成一棵树的结构,不过这棵树结构和之前所学的树结构都是不同的,并查集中的树结构是孩子指向父亲的。

在这里有一个节点3,如果节点3和节点2连在一起,连接方式是3这个节点指向2这个节点,2其实是整棵树的根节点,对于2来说,由于它是根节点,它也有一个指针指向自己。

这种情况下,节点1所代表的元素要和节点3所代表的元素合并,合并操作是怎么做的呢?实际上就是让1对应的指针指向3所在的这颗树的根节点,也就是让1指向2。

在并查集中可能存在一棵树(根节点为5的树,6和7为孩子节点都指向5),现在想让7这个元素和2这个元素合并,需要把7所在的根节点也就是5这个节点去指向2这个节点。

这就是我们实际实现并查集的思路。可以想象一下具体的存储所发生的变化,观察图可以看到,每一个节点其实只有一个指针,也就是只会指向另外一个元素,关于这个指针的存储依然可以使用数组的方式。

以10个元素为例的话,并查集开始就是这个样子,每一个节点都是根节点,指向自己,所以严格的来说并查集不是一棵树结构,而是一个森林。

森林就是里面有很多树,初始的情况下,现在我们这个森林中就有十棵树,每棵树都只有一个节点。

现在如果我们要进行union(4,3)这个操作,我们应该怎么做?其实就是将4这个节点它的指针去指向3这个节点就好了,数组中反应出来其实就是让parent(4)=3,这就代表4这个节点指向3这个节点。

下面如果我们再进行union(3,8)这个操作,让3这个节点指向8这个节点,数组中反应出来其实就是让parent(3)=8

如果再进行union(6,5),原理相同,依次类推……

再进行union(9,4),这里就有一个查询操作了,就要看一下4这个节点所在的根节点是谁呢?这个查询过程其实就是4指向3,3指向8,而8自己指向8,说明8是一个根节点,就找到了4的根节点是8,下面让9这个节点指向8这个节点就好了。

接下来依次进行union(2,1),union(5,0),union(7,2),union(6,2)

这就是我们并查集真正的实现方式。

代码实现

// 我们的第二版Union-Find
public class UnionFind2 implements UF {

    // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
    // parent[i]表示第一个元素所指向的父节点
    private int[] parent;
    private int size;  // 数据个数

    // 构造函数
    public UnionFind2(int size){

        parent = new int[size];
        this.size = size;
        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for( int i = 0 ; i < size ; i ++ )
            parent[i] = i;
    }

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

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

        // 不断去查询自己的父亲节点, 直到到达根节点
        // 根节点的特点: parent[p] == p
        while(p != parent[p])
            p = parent[p];
        return p;
    }

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

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

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        parent[pRoot] = qRoot;
    }
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(10.3)Quick Union
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00