有趣的算法（六） ——Find-Union算法
有趣的算法（六） ——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