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

相关文章

来自专栏编程

用户输入input&int

1、input():让程序暂停,等待用户输入一些文本,获取用户输入后再执行下一行代码,例如: car = input("请问你需要租什么样的车:") print...

1870
来自专栏漫漫深度学习路

简单介绍 protocol buffer

protocol buffer protocol buffer 是谷歌的一款序列化结构数据的工具. 它有几个核心的概念: .proto文件: 定义proto...

1826
来自专栏小樱的经验随笔

C/C++中int128的那点事

最近群友对int128这个东西讨论的热火朝天的。讲道理的话,编译器的gcc是不支持__int128这种数据类型的,比如在codeblocks 16.01/Dev...

1011
来自专栏noteless

[二十五]JavaIO之RandomAccessFile

683
来自专栏Java Edge

Redis数据类型StringListsSetsHashes

Redis中最基本的类型。 Redis中的String 类型是二进制安全的,也就是说在Redis中String类型可以包含各种数据,比如一张JPEG图片或者是...

792
来自专栏技术博文

让Json更懂中文(JSON_UNESCAPED_UNICODE)

我们知道, 用PHP的json_encode来处理中文的时候, 中文都会被编码, 变成不可读的, 类似”\u***”的格式, 还会在一定程度上增加传输的数据量....

2625
来自专栏JackieZheng

Hadoop阅读笔记(六)——洞悉Hadoop序列化机制Writable

  酒,是个好东西,前提要适量。今天参加了公司的年会,主题就是吃、喝、吹,除了那些天生话唠外,大部分人需要加点酒来作催化剂,让一个平时沉默寡言的码农也能成为一个...

1945
来自专栏钟绍威的专栏

java.io.StreamCorruptedException: invalid type code: AC错误的解决方法

问题描述: 在向一个文件写入可序列化对象时,每次只想向文件的末尾添加一个可序列化的对象,于是使用了FileOutputStream(文件名,true)间接的构建...

18110
来自专栏noteless

[八]JavaIO之FileInputStream 与 FileOutputStream

接下来介绍 FileInputStream  和 FileOutputStream

923
来自专栏散尽浮华

shell脚本之特殊符号总结性梳理

# 井号 (comments) 这几乎是个满场都有的符号 #!/bin/bash 井号也常出现在一行的开头,或者位于完整指令之后,这类情况表示符号后面的是注...

17910

扫码关注云+社区