【数据结构】并查集

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操作时间开销都很低。

对于并查集的优化：核心思想就是尽可能让树变矮。