有趣的算法(六) ——Find-Union算法

有趣的算法(六)——Find-Union算法

(原创内容,转载请注明来源,谢谢)

一、场景

Find-Union解决一类问题:

1、武林帮派

假设有n个武林帮派,当两个帮派是合作的时候,人员不会互相打架;如果两个帮派没有合作,则人员会打架。另有一个原则,假设帮派a和b合作,b和c合作,则a和c也算作合作。

现两个人相遇,需要快速知道其属于哪个帮派,是否会打架。另外,帮派之间也会再合作。

2、问题抽象

现有数字0~n-1,共n个数字。初始状态下,每个数字都是独立的组,每个数字叫做一个节点。接着数字之间会开始连接。当两个数字要连接的时候,要判断其是否已经连接(有可能是通过和其他数字进行的连接),如果没有连接则连接。

最终,经过一番连接,需要获取集合的数目(初始是n个,随着连接集合变少),以及在同一个集合中的元素。

二、分析

解决问题的关键,在于连接、判断是否已连接,这也就是find、union两个词的精髓。可以通过数组存放对应关系,每个数组的下标表示当前的点,可以利用数组进行find和union的操作。

现假设数组名id,元素n个,作为下面解决方案的前提。

三、解决方案

1、方法一:quick-find

第一个想法,id[i]存放的是第i个元素所属的组,初始id[i]=i。当两个元素要连接,则判断id[i]和id[j]是否一样,如果一样表示已经连接,如果不一样,则将id[i](或id[j])以及所有值等于id[i]的节点的值,都改成id[j]。

这样find速度非常快,因为是key-value。但是,问题在于,每一次union,都需要遍历整个id数组,并把值是id[i]的全部改掉,而无论当前有几个值是id[i]的节点。

当数组元素非常多的情况下,union将非常慢。

2、方法二:quick-union

为了加快union,现换一种思路。id[i]的值表示的是节点i的父节点。初始状态下,每个节点id[i]=i,表示自己指向自己的节点是根节点。当节点与其他节点连接的时候,id[i]的值会改成相应节点的下标。

所有节点用树的形式连接。当需要比较两个节点是否已经连接,只需要回溯这个链接的根节点即可。根节点一致的两个节点,表示两个已经连接的节点。

find的核心代码:

while(parentValue != this.id[currentIndex]){parentValue =this.id[currentIndex];}

此时,需要union则比较容易,只需要将其中一边节点的根节点,指向另一边节点的根节点,则两边所有的节点都连接在一起。

union核心代码:

Integer i = this.find(p);
Integer j = this.find(q);
id[j] = i;

这样的速度已经较快,但是存在的问题是,这样的连接是随意将两个节点进行连接。如果一边的节点很多,而要连接到另一边,则会造成树的深度太大,导致find的时候,寻找父节点需要不断的回溯,降低速度。

3、方法三:加权的quick-union

为了解决上述问题,进行了一个改进,即在连接的时候,将树节点较少的那颗,连接到节点较多的那颗。这样可以保证大多数的节点的深度不要增加。

要这样做,需要加一个数组,保存每个节点的子节点数量,初始状态都是1。当连接的时候,子节点数量少的一个连接到多的那个(相同时随意),并把多的那个的子节点数量再加上少的那个子节点。

    if(this.childNum[i] > this.childNum[j]){
       id[j] = i;
       this.childNum[i] += this.childNum[j];
    }else{
       id[i] = j;
       this.childNum[j] += this.childNum[i];
}

4、方法四:压缩路径的加权quick-union

方法三的速度已经很快,还有一个地方可以进行微调。即每次find的时候,由于其都在追溯父节点,则可以把每次追溯到的父节点,都指向要连接的那个根节点。

这样,可以让树更加扁平化,更加快find速度。

5、分析图

四、代码

1、Java版本

packagecom.lin.service.algorithm;
public classFindUnionService {
    private Integer count;//当前连接集合数量
    private Integer[] id;//节点父连接数组
    private Integer[] childNum;//节点的子节点
    private Integer[][] connectPairs;//待处理的连接数组
    public FindUnionService(Integer nodeNum,String strPairs){
        this.count = nodeNum;
        this.id = new Integer[this.count];
        this.childNum = newInteger[this.count];
        createArray();
        dealConnectPairs(strPairs);
        getUnion();
    }
    private void createArray(){
        //创建初始化节点和子节点数目
        for(int i=0;i<this.count;i++){
            this.id[i] = i;
            this.childNum[i] = 1;
        }
    }
    private void dealConnectPairs(StringconnectPairs){
        //创建待连接的数字
        //如果以竖线为分隔符,则split的时候需要加上两个斜杠【\\】进行转义
        String[] pairs =connectPairs.split("\\|");
        Integer pairsNum = pairs.length/2;
        this.connectPairs = newInteger[pairsNum][2];
        for(int i=0,j=0;i<pairsNum;i++){
            this.connectPairs[i][0] =Integer.parseInt(pairs[j++]);
            this.connectPairs[i][1] =Integer.parseInt(pairs[j++]);
        }
    }
    public Integer getCount(){return count;}
    public Integer[] getId(){return id;}
    public Integer[] getChildNum(){returnchildNum;}
    private Integer find(int currentIndex){
        //循环查找父节点
        int parentValue = currentIndex;
        while(parentValue !=this.id[currentIndex]){
            parentValue =this.id[currentIndex];
        }
        //路径压缩,将节点的全部父节点都指向r,把路径压缩成深度是1的树
        int parentIndex = currentIndex, tmp;
        while(parentIndex != parentValue){
            tmp = this.id[parentIndex];
            this.id[parentIndex] = parentValue;
            parentIndex = tmp;
        }
        return parentValue;
    }
    public Boolean connected(int p, intq){return find(p) == find(q);}
    private void getUnion(){
        for (Integer[] connectPair :this.connectPairs) {
            this.union(connectPair[0],connectPair[1]);
        }
    }
    private void union(int p, int q){
        Integer i = this.find(p);
        Integer j = this.find(q);
        if(!i.equals(j)){
            if(this.childNum[i] >this.childNum[j]){
                id[j] = i;
                this.childNum[i] +=this.childNum[j];
            }else{
                id[i] = j;
                this.childNum[j] +=this.childNum[i];
            }
            this.count--;
        }
    }
}

2、PHP版本

<?php
classFindUnion{
    private $count;//当前连接集合数量
    private $id;//节点父连接数组
    private $childNum;//节点的子节点
    private $connectPairs;//待处理的连接二维数组
    public function __construct($nodeNum,$strPairs){
        $this->count = $nodeNum;
        $this->id = array();
        $this->childNum = array();
        $this->connectPairs = array();
        $this->createArray();
        $this->dealConnectPairs($strPairs);
        $this->getUnion();
    }
    private function createArray(){
        //创建初始化节点和子节点数目
        for($i=0;$i<$this->count;$i++){
            $this->id[$i] = $i;
            $this->childNum[$i] = $1;
        }
    }
    private functiondealConnectPairs($connectPairs){
        //创建待连接的数字
        $pairs = explode('|', $connectPairs);
        $pairsNum = strlen($pairs)/2;
        for($i=0,$j=0;$i<$pairsNum;$i++){
            $this->connectPairs[$i][0] =intval($pairs[$j++]);
            $this->connectPairs[$i][0] =intval($pairs[$j++]);
        }
    }
    public function getCount(){return $count;}
    public function getId(){return $id;}
    public function getChildNum(){return$childNum;}
    private function find($currentIndex){
        //循环查找父节点
        $parentValue = $currentIndex;
        while($parentValue !=$this->id[$currentIndex]){
            $parentValue =$this->id[$currentIndex];
        }
        //路径压缩,将节点的全部父节点都指向r,把路径压缩成深度是1的树
        $parentIndex = $currentIndex;
        $tmp = 0;
        while($parentIndex != $parentValue){
            $tmp = $this->id[$parentIndex];
            $this->id[$parentIndex] =$parentValue;
            $parentIndex = $tmp;
        }
        return $parentValue;
    }
    public function connected($p, $q){return$this->find($p) == $this->find($q);}
    private function getUnion(){
        foreach($this->connectPairs as$connectPair) {
            $this->union($connectPair[0],$connectPair[1]);
        }
    }
    private function union($p, $q){
        $i = $this->find($p);
        $j = $this->find($q);
        if($i != $j){
            if($this->childNum[$i] >$this->childNum[$j]){
                $id[$j] = $i;
                $this->childNum[$i] +=$this->childNum[$j];
            }else{
                $id[$i] = $j;
                $this->childNum[$j] +=$this->childNum[$i];
            }
            $this->count--;
        }
    }
}

——written by linhxx 2017.10.11

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-10-11

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端笔记

【 数字游戏 2048 】原生 JavaScript 做小游戏

原生 JavaScript 2048 源码 : <!doctype html> <html> <head> <title>2048</title> <m...

39213
来自专栏小白客

每天学习一点儿算法--广度优先搜索

广度优先搜索(BFS)是我们学的第一种图算法,它可以让你找出两样东西之间的最短距离。 这里提到了一个新的概念:图, 那什么是图呢? 图简介 图用于模拟不同的东...

2874
来自专栏微服务生态

由学习《软件设计重构》所想到的代码review(二)

我们接第一篇来继续说明在代码review中,有哪些属于“层次结构”中的坏味道。 第一篇链接如下:http://www.jianshu.com/p/07dbf6...

792
来自专栏决胜机器学习

有趣的算法(三)——Hash算法

有趣的算法(三)——Hash算法 (原创内容,转载请注明来源,谢谢) 一、Hash算法 近期看到用hash实现基于hash的简单的小型数据库(传统大型数据...

3487
来自专栏Star先生的专栏

Tensorflow 术语表

本文主要简要介绍了广播操作、Graph(图)、Session(会话)、Tensor 等13个 Tensorflow 术语表。希望对大家了解学习 Tensorfl...

9411
来自专栏Coding01

链式编程

链式编程或者链式写法,是将多个方法 (函数) 通过点号 (.) 或者 (->)等符号链接在一起成为一句代码,这样不仅可以增强代码的可读性,而且每次链接,都是对对...

773
来自专栏ATYUN订阅号

使用Python建立你数据科学的“肌肉记忆”

你是否曾在在搜索语法时,因为打断了数据分析流而感到沮丧?为什么你在屡次查找后仍然不记得它?这是因为你还没有足够的练习来为它建立“肌肉记忆”。

662
来自专栏苦逼的码农

HashMap的存取原理你知道多少

在java的容器集合中,hashmap的使用频率可以说是相当高的。不过对于hashmap的存(put())以及取(get())的原理可能很多人还不大清楚,今天,...

1144
来自专栏我杨某人的青春满是悔恨

找零问题与动态规划

后来我发现在 leet code 也有类似的题,是个找零问题,就是不同面值的硬币组合成一个数有多少种情况。还挺有意思的,我就做了一下,用了递归:

851
来自专栏Golang语言社区

使用 Go 语言学会 Tensorflow

Tensorflow 并不是一个专门用于机器学习的库,相反的,它是一个通用的用于图计算的库。它的核心部分是用 C++ 实现的,同时还有其它语言的接口库。Go 语...

3002

扫码关注云+社区