最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 并查集(Union Find)

    我们之前学习的所有树结构都是由父亲指向孩子,但是并查集却是一种由孩子指向父亲的树结构这样一种数据结构,它可以非常高效的来解决连接问题(Connectivity Problem)

    如上这个图有非常多的点,每两个点之间有的有一个连接,有的没有连接,使用并查集就可以高效的回答这样一个问题:给出图中任意两点,问两点之间是否可以根据一个路径连接起来。

    连接问题

    网络中节点间的连接状态

    并查集可以非常快的判断网络中节点间的连接状态,这里的“网络”其实是一种抽象概念,不仅仅是互联网。

    最简单的例子,我们的社交网络无论是微博、Facebook,他们之间其实就是由一个个的人作为节点形成的一个网络,这种时候,我们就可以把每两个用户之间是好友关系这样的一个概念给抽象成是两个节点之间的边,如果我们可以这样的来建立一个网络的话,就会产生这样的问题,两个用户a和b,他们本来是互不认识的,通过网络我是否有可能通过我认识的人和我认识的人认识的人这样扩散最终接触到那位我本来完全不认识的人呢?

    这样一个问题就是在社交网络中的连接问题。

    数学中的集合类实现

    求两个集合的并集,并查集中的并本身也就是集合中的这个并,查也就是查询操作。

    实现并查集接口

    对于一组数据,主要支持两个动作:

    • union(p,q)
    • isConected(p,q)

    代码演示

    创建一个UnionFind接口UF.java

    public interface UF {
    
        int getSize();
        boolean isConnected(int p, int q);
        void unionElements(int p, int q);
    }
    

    源码下载

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

    导航目录

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

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(10.1)什么是并查集

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 108会员总数(位)
    • 3695资源总数(个)
    • 3本周发布(个)
    • 0 今日发布(个)
    • 181稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级