江小南

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操作构建树的时候,尽可能让树不长高。

  1. 用根结点的绝对值表示树的结点总数。
  2. 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