有趣的算法(六) ——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 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

浅谈UML的概念和模型之UML九种图

http://blog.csdn.net/jiuqiyuliang/article/details/8552956

321
来自专栏张善友的专栏

利用 Microsoft StreamInsight 控制较大数据流

原文地址:http://msdn.microsoft.com/zh-cn/magazine/hh205648.aspx 下载代码示例 生产线的产量下降后,将...

1736
来自专栏码匠的流水账

聊聊spring for kafka对consumer的封装与集成

本文主要解析一下spring for kafka对原生的kafka client consumer的封装与集成。

261
来自专栏linux驱动个人学习

处理器并行设计

1082
来自专栏比原链

剥开比原看代码05:如何从比原节点拿到区块数据?

Gitee地址:https://gitee.com/BytomBlockchain/bytom

221
来自专栏用户画像

3.2.3页面置换算法

进程运行时,若其访问的页面不在内存而徐将其调入,但内存已无空闲时间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区。 而选择调入页面的算法就称为页面置...

482
来自专栏Google Dart

AngularDart4.0 高级-层级依赖注入器 顶

在Dependency Injection指南中你学会了基础的Angular依赖注入. Angular有一个层级依赖注入 系统. 实际上是一个与组件树相平行的...

401
来自专栏区块链

理解区块链背后的Merkle Tree

利用了 Merkle tree 的区块链技术,现今受欢迎的程度不亚于比特币。需要跟踪数据并且保证数据一致性的企业也开始看到区块链技术对这一过程的帮助。

1.7K13
来自专栏Danny的专栏

Entity Framework学习笔记——EF简介(一篇文章告诉你什么是EF)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

553
来自专栏精讲JAVA

Netty 实现原理浅析

(点击上方公众号,可快速关注) 来源:kafka0102的博客 , www.kafka0102.com/2010/06/167.html Netty是JBoss...

2158

扫描关注云+社区