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

数据结构笔记总结(10.7)更多和并查集相关的话题

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

改进第六版的并查集

借助递归实现查询一个节点的时候,将这个节点以及这个节点之前的所有节点全都直接指向根节点。

// 我们的第六版Union-Find
public class UnionFind6 implements UF {

    // rank[i]表示以i为根的集合所表示的树的层数
    // 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
    // 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
    private int[] rank;
    private int[] parent; // parent[i]表示第i个元素所指向的父节点
    private int size;    // 数据个数

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

        rank = new int[size];
        parent = new int[size];
        this.size = size;

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

    @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.");

        // path compression 2, 递归算法
        if(p != parent[p])
            parent[p] = find(parent[p]);
        return parent[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;

        // 根据两个元素所在树的元素个数不同判断合并方向
        // 将元素个数少的集合合并到元素个数多的集合上
        if( rank[pRoot] < rank[qRoot] )
            parent[pRoot] = qRoot;
        else if( rank[qRoot] < rank[pRoot])
            parent[qRoot] = pRoot;
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // 此时, 我维护rank的值
        }
    }
}

接下来测试一下

我们使用递归的方式写的压缩比非递归的方式整体性能上还是差一点点,这是因为在递归的过程中是有相应的开销的。

不仅如此,其实对于我们之前的第五版的路径压缩来说,也并不是不能做到让所有的节点都直接指向根节点,只不过是不能一次性做到而已。

并查集的时间复杂度分析

无论是查询操作还是合并操作都是O(h)级别,这个h是树的高度,不过这个时间复杂度并不能反映h和n之间的关系。

而对于并查集来说,它不是一个严格的二叉树或者几叉树,所以其实也没有h严格意义上它是某个log(n)级别。整体复杂度分析比较复杂。

加入了路径压缩后,时间复杂度是O(logn)

源码下载

下载地址

导航目录

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

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

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

客服QQ


QQ:2248886839


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