数据库技术:并查集

并查集的定义

并查集：一种维护集合的数据结构，合并(Union)，查找(Find)，集合(Set)

1. 合并：合并两个集合
2. 查找：判断两个元素是否在一个集合
   并查集实现——用一个数组

int father[N}; 

father[i]表示元素i的父亲结点，而父亲结点也是这个集合的元素(1<=i<=N)。
father[i]=i：元素i是该集合的根结点
同一集合来说只存在一个根结点，且将其作为所属集合的标识

father[1] = 1; //1的父亲结点是自己，即根结点 father[2] = 1; //2的父亲结点是1 father[3] = 2; //3的父亲结点是2 father[4] = 2; //4的父亲结点是2 father[5] = 5; //5的父亲结点是自己，即根结点 father[6] = 6; //6的父亲结点是5 

并查集的基本操作

1. 初始化
   每个元素都是独立的一个集合，需要令所有father[i]=i

for(int i = 1; i <= N; i++) {     father[i] = i; //令father[i]为-1也可，此处以father[i] = i为例 } 

2. 查找
   对给定的结点寻找其根结点的过程

//findFather函数返回元素x所在集合的根结点 int findFather(int x) {     while(x != father[x]) //如果不是根结点，继续循环     {         x = father[x]; //获得自己的父亲结点     }     return x; } 

也可以用递归实现

int findFather(int x) {     if(x == father[x])         return x; //如果找到根结点，则返回根结点编号x     else         return findFather(father[x]); //否则，递归判断x的父亲结点是否是根结点 } 

3. 合并
   把两个集合合并成一个集合。
   先判断两个元素是否属于同一个集合，只有当两个元素属于不同集合时合并，把其中一个集合的根结点的父亲指向另一个集合的根结点。
   1）对于给定的两个元素a、b，判断它们是否属于同一集合。调用上面的查找函数，对a、b分别查找根结点，然后再判断其根结点是否相同。
   2）合并两个集合：在1）中已经获得两个元素的根结点faA与faB，因此只需要把其中一个的父亲结点指向另一个结点。father[faA]=faB
   
   1）判断元素4和元素6是否属于同一个集合：元素4所在集合的根结点是1，元素6所在集合的根结点是5，不属于同一集合
   2）合并两个集合：令father[5]=1，把元素5的父亲设为元素1

void Union(int a, int b) {     int faA = findFather(a); //查找a的根结点，记为faA     int faB = findFather(b); //查找b的根结点，记为faB     if(faA != faB) //如果不属于同一个集合     {         father[faA] = faB; //合并它们     } } 

并查集产生的每一个集合都是一棵树。

路径压缩

把当前查询结点的路径上的所有结点的父亲都指向根结点

1. 按原来的写法获得x的根结点r
2. 重新从x开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点r

int findFather(int x) {     //由于x在下面的while中会变成根结点，因此先把原先的x保存一下     int a = x;     while(x != father[x]) //寻找根结点     {         x = father[x];     }     //到这里，x存放的是跟结点。下面把路径上所有结点的father都改成根结点     while(a != father[a])     {         int z = a; //因为a要被father[a]覆盖，所以先保存a的值，以修改father[a]         a = father[a]; //a回溯父亲结点         father[z] = x; //将原先的结点a的父亲改成根结点x     }     return x; //返回根结点 } 

递归写法

int findFather(int v) {     if(v == father[v])         return v; //找到根结点     else     {         int F = findFather(father[v]); //递归寻找father[v]的根结点F         father[v] = F; //将根结点F赋给father[v]         return F; //返回根结点F     } }  

需要了解更多数据库技术:并查集，都可以关注数据库技术分享栏目—编程笔记