详解Java实现数据结构之并查集

​一、什么是并查集

对于一种数据结构,肯定是有自己的应用场景和特性,那么并查集是处理什么问题的呢?

并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题,常常在使用中以森林来表示。在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。

你可能还有点迷糊并查集能怎么玩,看完这篇然后回头看这两个问题(分别杭电1232和杭电1272)。

问题1:

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?

这个问题很容易,给定的关系看看需要合并多少次就知道最少的建设道路数量。

问题二:

小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。

为什么不直接操作a,b而是要找到他们的父亲进行操作?

原因1是因为a,b可能是叶子节点,其值是正的表示已经有父亲了,如果直接操作会使其与原来的集合分离开。另外集合中的数量(负数)也不能有效叠加。

原因2是因为合并的时候如果合并如果a,b是非根节点操作,可能会造成这个树的深度太大,不利于集合a中的查询效率。

2.3、查 search(int a)

查询,其实就是查询这个节点的根节点是啥(也称代表元),这个过程也有点类似递归的过程,叶子节点值如果为正,那么就继续查找这个值得位置的结果,一直到值为负数的时候说明找到根节点,可以直接返回。

不过在查询的过程中可以顺便路径优化,这样在频繁查询能够大大降低时间复杂度。

三、优化

你以为上面的就是并查集的全部?不不不,并查集还有不少需要掌握嘞,估计细心的人可能也会发现一些问题。

你可能会有疑问:

如何查看a,b是否在同一个集合?

查看是否在一个集合,只需要查看节点根祖先的结果是否相同即可。因为只有根的数值是负的,而其他都是正数表示指向的元素。所以只需要一直寻找直到不为正数进行比较即可!

a,b合并,究竟是a的祖先合并在b的祖先上,还是b的祖先合并在a上?

这里会遇到两种情况,这个选择也是非常重要的。你要弄明白一点:树的高度+1的化那么整个元素查询的效率都会降低!

所以我们通常是:小树指向大树(或者低树指向高树),这个使得查询效率能够增加!

当然,在高度和数量的选择上,还需要你自己选择和考虑。

查找途中能不能路径压缩:

每次查询,自下向上。当我们调用递归的时候,可以顺便压缩路径(将当前数组的值等于递归返回的根节点的值),我们查找一个元素只需要直接找到它的祖先,所以当它距离祖先近那么下次查询就很快。并且压缩路径的代价并不大!

试想一下,如果一个分支的深度为1000,不压缩路径那么这个分支每个节点平均查找次数为500,压缩一次下次再查找就是1次。

学会路径压缩,你基本可以秒杀大部分并查集的题。

四、代码实现

并查集实现起来较为简单,直接贴代码!

import java.util.Scanner;
public class DisjointSet {
    static int tree[]=new int[100000];//假设有500个值
    public DisjointSet()    {set(this.tree);}
    public DisjointSet(int tree[]) 
    {
        this.tree=tree;
        set(this.tree);
    }
  //初始化所有都是-1 有两个好处,这样他们指向-1说明是自己,
  //第二,-1代表当前森林有-(-1)个
    public void set(int a[])
    {
        int l=a.length;
        for(int i=0;i<l;i++)
        {
            a[i]=-1;
        }
    }
    public int search(int a)//返回头节点的数值
    {
        if(tree[a]>0)//说明是子节点
        {
            return tree[a]=search(tree[a]);//路径压缩
        }
        else
            return a;
    }
    public int value(int a)//返回a所在树的大小(个数)
    {
        if(tree[a]>0)
        {
            return value(tree[a]);
        }
        else
            return -tree[a];
    }
    public void union(int a,int b)//表示 a,b所在的树合并
    {
        int a1=search(a);//a根
        int b1=search(b);//b根
        if(a1==b1) {System.out.println(a+"和"+b+"已经在一棵树上");}
        else {
        if(tree[a1]<tree[b1])//这个是负数,为了简单减少计算,不在调用value函数
        {
            tree[a1]+=tree[b1];//个数相加  注意是负数相加
            tree[b1]=a1;       //b树成为a的子树,直接指向a;
        }
        else
        {
            tree[b1]+=tree[a1];//个数相加  注意是负数相加
            tree[a1]=b1;       //b树成为a的子树,直接指向a;
        }
        }
    }
    public static void main(String[] args)
    {       
        DisjointSet d=new DisjointSet();
        d.union(1,2);
        d.union(3,4);
        d.union(5,6);
        d.union(1,6);

        d.union(22,24);
        d.union(3,26);
        d.union(36,24);
        System.out.println(d.search(6));    //头
        System.out.println(d.value(6));     //大小
        System.out.println(d.search(22));   //头
        System.out.println(d.value(22));     //大小
    }
}

五、结语

并查集属于简单但是很高效率的数据结构。在集合中经常会遇到。如果不采用并查集而传统暴力效率太低,而不被采纳。

以上就是详解Java实现数据结构之并查集的详细内容,更多关于Java 数据结构 并查集的资料请关注179885.Com其它相关文章!

猜你在找的详解Java实现数据结构之并查集相关文章

并查集这种数据结构,可能出现的频率不是那么高,但是还会经常性的见到,其理解学习起来非常容易,通过本文,一定能够轻轻松松搞定并查集
了使用feign服务调用添加Header参数的操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
IDEA 功能强大,可以用来高效的开发应该程序。它还支持第三方插件、用户可以根据需要添加自己喜欢的插件。下面介绍如何使用 IDEA 创建 Spring Cloud 项目
里氏替换原则是用来帮助我们在继承关系中进行父子类的设计。它阐述了有关继承的一些原则,也就是什么时候应该使用继承,什么时候不应该使用继承,以及其中蕴含的原理。
责任链模式是一种行为设计模式,允许你将请求沿着处理链发送,然后处理者都可对其进行处理,完成后可以再将其传递给下一个处理者。下面将会举例说明什么是责任链模式,责
了多模块项目引入SpringSecurity后一直报404的解决方案,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
了SpringSecurity整合jwt权限认证的全流程讲解,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
XSS攻击全称跨站脚本攻击,是一种在web应用中的计算机安全漏洞,允许恶意web用户将代码植入到提供给其它用户使用的页面中。本文介绍防止XSS攻击的方法
所谓模板方法模式,就是一个对模板的应用,就好比老师出试卷,每个人的试卷都是一样的,这个原版试卷就是一个模板,可每个人写在试卷上的答案都是不一样的,这就是模板方法模
了如何解决springcloud feign 首次调用100%失败的问题,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
今天给大家带来的是关于Java源码的相关知识,文章围绕着Java ImmutableMap展开,文中有非常详细的介绍及代码示例,需求的大佬可以参考下
了浅谈Ribbon、Feign和OpenFeign的区别。具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教