06--图解数据结构之并查集

连接问题--网络中节点间的连接状态 节点、边--isConnrcted(p,q) 集合的并集---union(p,q)

并查询连接.png

并查集接口

/**
 * 作者:张风捷特烈
 * 时间:2018/9/25 0025:11:09
 * 邮箱:1981462002@qq.com
 * 说明:并查集接口
 */
public interface IUF {
    /**
     * 查看p,q元素是否属于同一集合
     *
     * @param p p元素
     * @param q q元素
     * @return 是否属于同一集合
     */
    boolean isConnected(int p,int q);

    /**
     * 联合p,q所在集合
     * @param p p元素
     * @param q q元素
     */
    void unionEl(int p, int q);

    /**
     * 元素个数
     * @return 元素个数
     */
    int size();
}

第一版:快速查询的并查集

/**
 * 作者:张风捷特烈
 * 时间:2018/9/25 0025:11:15
 * 邮箱:1981462002@qq.com
 * 说明:快速查询并查集
 */
public class QuickFindUF implements IUF {

    private int[] id;

    public QuickFindUF(int size) {
        id = new int[size];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    @Override
    public boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    @Override
    public void unionEl(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID) {
            return;
        }
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pID) {
                id[i] = qID;
            }
        }
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= id.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        return id[p];
    }

    @Override
    public int size() {
        return id.length;
    }
}

isConnected方法复杂度O(1) unionEl方法复杂度O(n)


第二版:快速合并并查集

/**
 * 作者:张风捷特烈
 * 时间:2018/9/25 0025:11:15
 * 邮箱:1981462002@qq.com
 * 说明:快速合并并查集
 */
public class QuickUnionUF implements IUF {
    private int[] parent;

    public QuickUnionUF(int size) {
        parent = new int[size];
        //每个节点都是一颗树
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionEl(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }


        parent[pRoot] = qRoot;
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int size() {
        return parent.length;
    }
}

基于树实现,isConnected和unionEl的复杂度O(logn),但有可能退化到O(n)


第三版:改良型----基于集合节点数连接

/**
 * 作者:张风捷特烈
 * 时间:2018/9/25 0025:11:15
 * 邮箱:1981462002@qq.com
 * 说明:快速合并并查集优化
 */
public class QuickUnion2UF implements IUF {
    private int[] parent;
    /**
     * 以treeSize[i]为根的集合元素个数
     */
    private int[] treeSize;

    public QuickUnion2UF(int size) {
        parent = new int[size];
        treeSize = new int[size];
        //每个节点都是一颗树
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            treeSize[i] = 1;
        }
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionEl(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (treeSize[pRoot] < treeSize[qRoot]) {
            parent[pRoot] = qRoot;
            treeSize[qRoot] += treeSize[pRoot];
        } else {
            parent[qRoot] = pRoot;
            treeSize[pRoot] += treeSize[qRoot];
        }
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int size() {
        return parent.length;
    }
}

第三版:改良型----基于集合树深数连接

/**
 * 作者:张风捷特烈
 * 时间:2018/9/25 0025:11:15
 * 邮箱:1981462002@qq.com
 * 说明:快速合并并查集优化
 */
public class QuickUnion3UF implements IUF {
    private int[] parent;
    /**
     * 以rank[i]为根的集合元素个数
     */
    private int[] rank;

    public QuickUnion3UF(int size) {
        parent = new int[size];
        rank = new int[size];
        //每个节点都是一颗树
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionEl(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 {
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int size() {
        return parent.length;
    }
}

时间分析:

unionEl方法册数测试:size=10000

方法\数量

复杂度

1000

10000

10W

100W

1000W

QuickFindUF

O(n)

0.0197秒

0.0880秒

0.1199秒

0.1688秒

0.5216秒

QuickUnionUF

O(logn)

0.0015秒

0.0132秒

0.7418秒

7.0839秒

----秒

quickUnion2UF

O(logn)

0.0017秒

0.0050秒

0.0220秒

0.0966秒

0.6657秒


unionEl方法册数测试:size=100000

方法\数量

复杂度

1000

10000

10W

100W

1000W

QuickFindUF

O(n)

0.0197秒

0.0880秒

0.1199秒

0.1688秒

10.0468秒

QuickUnionUF

O(logn)

0.0015秒

0.0132秒

0.7418秒

7.0839秒

----秒

quickUnion2UF

O(logn)

0.0017秒

0.0050秒

0.0220秒

0.0966秒

0.8478秒


unionEl方法册数测试:size=1000000

方法\数量

复杂度

1000

10000

10W

100W

1000W

QuickFindUF

O(n)

0.6346秒

5.3409秒

----秒

----秒

----秒

QuickUnionUF

O(logn)

0.0012秒

0.0052秒

0.0281秒

----秒

----秒

quickUnion2UF

O(logn)

0.0013秒

0.0062秒

0.0304秒

0.2186秒

1.8915秒


unionEl方法册数测试:size=10000000

方法\数量

复杂度

1000

10000

10W

100W

1000W

quickUnion2UF

O(logn)

0.0013秒

0.0063秒

0.0335秒

0.1903秒

2.5726秒

quickUnion3UF

O(logn)

0.0016秒

0.0060秒

0.0323秒

0.1932秒

2.5327秒


后记、

1.声明:

[1]本文由张风捷特烈原创,各图均由本人亲自所画,转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正 [4]你的喜欢与支持将是我最大的动力

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联网杂技

前端异步代码解决方案实践(二)

早前有针对 Promise 的语法写过博文,不过仅限入门级别,浅尝辄止食而无味。后面一直想写 Promise 实现,碍于理解程度有限,多次下笔未能满意。一拖再拖...

25060
来自专栏轮子工厂

一篇文章帮你解决中文乱码问题---JavaWeb中文编码问题全面解析

这就是为什么我们在浏览器的地址栏中能看到中文,但是把地址拷贝出来后中文就变成了一些奇怪的串了。

89340
来自专栏Python小屋

Python处理文本文件案例一则

问题描述:当前文件夹中有一文件data.txt,其中包含一些自然数,每行一个。要求编写程序,读取data.txt中的所有自然数,将其升序排序之后写入新文件dat...

14130
来自专栏源哥的专栏

XML文件解析

在现在很多采用java开发的基于b/s结构的系统中,经常将一些配置参加放到一个xml文件中,然后在这个文件中取参数,这样减少了hard code的情况。下面这个...

10120
来自专栏desperate633

共享资源的线程安全性Local VariablesLocal Object ReferencesObject Member VariablesThe Thread Control Escape Rul

如果某段代码可以正确的被多线程并发的执行,那么我们就称这段代码是线程安全的,如果一段代码是线程安全的那么他肯定不会出现资源竞速的问题。资源竞速的问题只发生在多个...

6210
来自专栏游戏杂谈

describeType的使用

describeType函数在adobe官方在线文档上的定义如下:生成描述ActionScript对象(命令为方法的参数)的XML对象,此方法实现ActionS...

10430
来自专栏喵了个咪的博客空间

zephir-(8)类和对象1

#zephir-类和对象1# ? ##前言## 先在这里感谢各位zephir开源技术提供者 zephir全面使用对象编程,这就是为什么拓展的使用方式只能是方法和...

29330
来自专栏前端菜鸟变老鸟

ES6(二):Promise

ES6之前解决异步编程只能使用回调函数或事件,ES6中加入了 Promise,使得异步编程更加简洁直观和合理

13430
来自专栏null的专栏

挑战数据结构和算法——整数的二进制表示中1的个数

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题涉及到二进制的处理,在本题使用到&操作和>>操作...

34060
来自专栏程序你好

在c#中,如何序列化/反序列化一个字典对象?

.Net提供的各种序列化的类,通过使用这些类,. Net对象的序列化和反序列化变得很容易。但是字典对象的序列化并不是那么容易。为此,您必须创建一个能够序列化自身...

12710

扫码关注云+社区

领取腾讯云代金券