算法——union-find

简介

今天跟大家分享一个算法,如题union-find。这个算法要解决的就是一个动态连通性问题,什么是动态连通性呢?首先是连通性,给出两个对象,可以判断两个对象是否相连;再有就是动态,如若给出的两个对象不相连,我们可以将他们连起来,于是连通的对象发生了变化,体现了动态。举个栗子来说,就像判断两个计算机能否实现通信,就是判断他们是否能够通过现有的线路相连,进行通信,如果不能通信就需要通过其他手段,如增加物理线路,增加路由等来使得两个计算机实现连接。在下边的叙述中,为了方便起见,我们把一个一个对象,或者一个一个计算机称为触点,相连的几个触点整体称为连通分量(简称分量)

上面这个图有九个触点,三个分量

正文

首先给出初步算法实现:

public class UF {
    private int[] id;//分量id
    private int count;//分量数量
    public UF(int N){
        count = N;
        id = new int[N];
        for (int  i=0;i<N;i++){
            id[i] = i;
        }
    }
    public int count(){
        return count;
    }
    public boolean connected(int p,int q){
        return find(p) == find(q);
    }
    public int find(int i){
        return id[i];
    }
    public void union(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;
        }
        count--;
    }
   public static void main(String[] args) {
        int[] array = {4,3,3,8,6,5,9,4,2,1,8,9,5,0,7,2,6,1,1,0,6,7};
        UF uf = new UF(10);
        for (int i = 0;i<array.length-1;i=i+2){//A
            if (uf.connected(array[i],array[i+1])) continue;
            uf.union(array[i],array[i+1]);
            System.out.println("union"+array[i]+"and"+array[i+1]);
        }
        System.out.println("共"+uf.count()+"个连通分量");
    }
}

首先需要明白在这个实现中,id这个数组的索引代表的就是上文所说的触点。count表示的就是分量的数量。初始化时,有N个分量,每个分量中只有一个触点。判断两个触点i和j是否相连,就看id[i]和id[j]的值是否相等。最开始每个触点各成一个分量,于是都各不相连。当我们需要连接两个触点的时候,就要将值为id[i]的触点的值改为id[j](有点拗口,代码更清晰),当然反过来亦可。今天主要需要讨论的就是find和union的不同实现。上面这个实现被称为quick-find,顾名思义,显然find()方法的速度是很快的,它只需要访问id数组一次。但是,union()则需要扫描整个数组。当id[]过长,需要处理大量数据时,这个算法实现明显是不可以胜任的。

quick-union成为了下一步的探索

    public int find(int i){
        while (i!=id[i]) i = id[i];
        return i;
    }
    public void union(int p,int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot==qRoot) return;
        id[pRoot] = qRoot;
        count--;
    }

在quick-union这个实现中,union()不再需要遍历整个数组,看起来要比quick-find快很多。在这个算法实现中使用森林来组织所有的触点,相连的触点会组织成一棵树。不相连的触点就会位于不同的树上面。此算法中的find就是寻找触点的根触点(根触点就是id[i]=i的点),也就是树的根。union()就是判断两个触点是否是一颗树上的节点,如果不是,那就将一棵树作为子树连接到另一颗树上面。如下图所示,当运行main函数时,随着A处循环的进行,过程如下(公众号回复quick-union可查看动画演示)

可惜这个算法实现的效率跟输入的触点有很大的关系,比如,最坏情况下会出现这样的树

此时我们就需要再次改进算法,于是出现了加权quick-union算法

    private int find(int p){
        while (p != id[p])p = id[p];
        return p;
    }
    public void union(int p,int q){
        int j = find(p);
        int i = find(q);
        if (i == j) return;
        if (sz[i]<sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        }
        else {
            id[j] = i;
            sz[i] += sz[j];
        }
        count--;
    }

这个算法改进的一点就是在连接两颗树的时候,先判断树的大小,保证将小数连在大树上,从而减小树的深度,提高效率。在这个算法中新增了一个实例变量sz[],这个数组用来保存每个树的大小,从而方便操作。

此时这个算法已经可以处理大量的数据了。但没有最好,只有更好,更优秀的算法实现送给大家----使用路径压缩的加权quick-union算法

  private int find(int p){
        while (p != id[p])
        {
        id[p] = id[id[p]]
        p = id[p];
        }
        return p;
    }

只是在find()方法中加了一行代码,这行代码的用处就是将p的父节点设置成他的爷爷节点,最终P就会直接连在根节点上,从而路径被压缩,再次提高了效率。

这里没有用数学语言严谨的讨论每种实现的效率,复杂度等。各种算法的时间复杂度如下:

参考自《算法》,需要pdf版书籍请公众号直接回复 算法

如果您喜欢这篇文章,期待您的关注

本文分享自微信公众号 - Vegout(t10244201)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-02-19

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据学习交流

大数据开发之常见九种数据分析方法

今天给大家分享一篇关于大数据开发常见的9种数据分析方法,首先数据分析是从数据中提取有价值信息的过程,过程中需要对数据进行各种处理和归类,只有掌握了正确的数据分类...

22430
来自专栏Bingo的深度学习杂货店

【DP、双指针】5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume th...

11630
来自专栏中科院渣渣博肆僧一枚

python中各种数据类型之间的转换

由于 json 语法规定 数组或对象之中的字符串必须使用双引号,不能使用单引号 (官网上有一段描述是 “A string is a sequence of ze...

49120
来自专栏慕容千语的架构笔记

Java程序员进阶架构师的五个阶段,你到了哪各阶段?

之前有个讨论:实现同样功能,简洁代码一定比复杂代码效率高吗?有的说,还得看算法,如果算法相同,简洁代码效率应该会高一些。有的说,即使算法相同,简洁代码也不见得比...

14720
来自专栏中科院渣渣博肆僧一枚

Python字符串操作之字符串分割与组合

12.1 str.split():字符串分割函数 通过指定分隔符对字符串进行切片,并返回分割后的字符串列表。 语法:

14020
来自专栏Unity游戏开发

基于反射、泛型的不定参数、不定类型的排序

方法相关 参数: string数组 - 全部要比较的字段名称 bool数组 - 每一个字段升序排序还是降序排序 IList<T>集合 - 要排序的Lis...

10630
来自专栏中科院渣渣博肆僧一枚

tf.parse_single_example

对于稠密张量,返回的张量与parse_example的输出相同,除了没有批处理维数,输出形状与dense_shape中给出的形状相同。

45110
来自专栏happyJared

HashMap 和 Hashtable 的区别

15720
来自专栏中科院渣渣博肆僧一枚

tf.train.Saver

Saver类添加ops来在检查点之间保存和恢复变量,它还提供了运行这些操作的方便方法。检查点是私有格式的二进制文件,它将变量名映射到张量值。检查检查点内容的最佳...

33320
来自专栏Java架构师进阶

@Autowired的使用:推荐对构造函数进行注释

Spring Team recommends "Always use constructor based dependency injection in you...

16410

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励