有趣的算法(六)——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