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

数据结构笔记总结(10.1)什么是并查集

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

并查集(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);
}

源码下载

下载地址

导航目录

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

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

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

客服QQ


QQ:2248886839


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