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

并查集(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)什么是并查集

Leave a Reply

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

立即加入 了解更多