【数据结构与算法】并查集基础

浏览数：40 / 时间：2015年06月08日

1、介绍

并查集是一种树型数据结构，用于处理一些不相交集合的合并问题。

并查集主要操作有：

　　（1）合并两个不相交集合；

　　（2）判断两个元素是否属于同一个集合；

　　（3）路径压缩；

2、常用操作

用father[i]表示元素i的父亲结点，例如：

技术分享

用某个元素所在树的根节点表示该元素所在集合；

判断两个元素是否属于同一个集合的时候，只需要判断他们所在树的根节点是否一样即可；

也就是说，当我们合并两个集合的时候，只需要在两个根节点之间连边即可。

获取根节点代码：

1 int findFather(int x){
2     if(father[x] == x)
3         return x;
4     else
5         return findFather(father[x]);
6 }

判断是否属于同一集合代码：

1 bool judge(int x,int y){
2     int fx,fy;
3     fx = findFather(x);
4     fy = findFather(y);
5     return fx==fy;
6 }

合并不同元素到同一集合代码：

1 void unionSet(int x,int y){
2     x = findFather(x);
3     y = findFather(y);
4     father[x] = y;
5 }

3、优化1——路径压缩

思想

每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快；

步骤

（1）找到根节点；

（2）修改查找路径上的所有结点，将他们都指向根节点；

例如查找下面并查集中的“20”，“9，10，20”均在查找路径上，则进行路径压缩

技术分享

带路径压缩的查找算法代码

 1 int findFather(int x){
 2     int r = x;
 3     //get the root of x
 4     while(father[r] != r)
 5         r = father[r];
 6     int i=x;
 7     //update the nodes in searching path
 8     while(i != r){
 9         j = father[i];
10         father[i] = r;
11         i = j;
12     }
13     return r;
14 }

4、优化2-合并

思想

两个集合合并，也就是2棵树合并，为了降低合并后的树的深度，一般采取将深度小的树的树根作为深度大的树的树根的孩子节点。

策略

增加辅助空间记录树的深度。

合并代码：

 1 void unionSet(int x,int y){
 2     x = findFather(x);
 3     y = findFather(y);
 4     if(x == y)
 5         return ;
 6     if(rank[x] > rank[y]){
 7         father[y] = x;
 8     }else{
 9         if(rank[x] == rank[y])
10             rank[y]++;
11         father[x] = y;
12     }
13 }