江
江小南
V1
2023/03/05阅读:28主题:萌绿
【数据结构】并查集
1. 集合

集合是一种逻辑结构,我们可以将集合元素划分为若干个互不相交的子集。
这样,就可以使用互不相交的树,表示多个“集合”。也就是我们前面说过的森林。

2. 查
问:如何“查”到一个元素到底属于哪一个集合?
答:从指定元素出发,一路向北,就可以找到根结点。
问:如何判断两个元素是否属于同一个集合?
—答:分别查到两个元素的根结点,判断根结点是否相同。
3. 并
问:如何把两个集合“并”为一个集合?
答:让一棵树成为另一颗树的子树即可。
重复这种操作,最后只剩下一棵树。
4. 并查集的存储结构
1. 树的存储——双亲表示法
双亲表示法:每个结点中保存指向双亲的“指针(数组下标)”。

#define MAX_TREE_SIZE 100 // 树中最多结点数
typedef struct{ // 树的结点定义
ElemType data; // 数据元素
int parent; // 双亲位置域
}PTNode;
typedef struct{ // 树的类型定义
PTNode nodes[MAX_TREE_SIZE]; // 双亲表示
int n; // 结点数
}PTree;
2. 并查集的存储结构
用一个数组S[]表示“集合”关系。
3. 并查集的基本操作
Find——“查”操作:确定一个指定元素所属集合。
Union——“并”操作:将两个不相交的集合合并为一个。
并查集是逻辑结构——集合的一种具体实现,只进行“并”和“查”两种基本操作。
#define SIZE 13
int UFSets[SIZE]; // 集合元素数组
// 初始化并查集
void Inital(int S[]){
for(int i=0;i<SIZE;i++){
S[i]=-1;
}
}
// Find “查”操作,找x所属集合(返回x所属根结点)
int Find(int S[],int x){
while(S[x]>=0){ // 循环找x的根
x=S[x];
}
return x; // 根的s[]小于0
}
// Union “并”操作,将两个集合合并为一个
void Union(int S[],int Root1,int Root2){
// 要求Root1与Root2是不同的集合
if(Root1==Roor2){
return;
}
// 将根Root2连接到另一个根Root1下面
S[Root2]=Root1;
}
时间复杂度分析:
对于查操作,最坏时间复杂度为O(n)。
对于并操作,时间复杂度为O(1)。
4. Union操作的优化
优化思路:在每次Union操作构建树的时候,尽可能让树不长高。
-
用根结点的绝对值表示树的结点总数。 -
Union操作,让小树合并到大树。

// Union “并”操作,小树合并到大树
void Union(int S[],int Root1,int Root2){}
if(Root1==Root2){
return;
}
if(S[Root2]>S[Root1]){ // Root2的结点数更少
S[Root1]+=S[Root2]; // 累加结点总数
S[Root2]=Root1; // 小树合并到大树
}else{
S[Root2]+=S[Root1]; // 累加结点总数
S[Root1]=Root2; // 小树合并到大树
}
}
该方法构造的树高不超过
Union操作优化后,Find操作最坏时间复杂度为:
5. Find操作优化
压缩路径:Find操作,先找到根结点,再将查找路径上所有结点都挂到根结点下。

说明:例如要找L结点,可以先找到L的根结点A,找根结点的过程中经过了E、B结点,那么将E、B、L结点同时挂到A结点上。
// Find “查”操作优化,先找到根结点,再进行“路径压缩”
int Find(int S[],int x){
int root=x;
while(S[Root]>=0){ // 循环找到根
root=S[Root];
}
while(x!=root){ // 压缩路径
int t=S[x]; // t指向x的父结点
S[x]=root; // x直接挂到根结点下
x=t;
}
return root; // 返回根结点编号
}
每次Find操作,先找根,再“压缩路径”,可使树的高度不超过0(a(n))。α(n)是一个增长很缓慢的函数,对于常见的n值,通常α(n)<4,因此优化后并查集的Find、Union操作时间开销都很低。
对于并查集的优化:核心思想就是尽可能让树变矮。
作者介绍
江
江小南
V1