并查集介绍 & 代码实现 & 优化思路详解

什么是并查集

并：合并；

查：查询；

集：集合

其实就是只用来进行 并 和 查 操作的集合。并查集常用来解决连通性问题。

通俗来讲：就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：

• 并：将两个元素添加到一个集合中。
• 查：判断两个元素在不在同一个集合

---

并查集的实现思路分析

1、用森林，表示集合特性

将一个个集合看作一棵棵树。

• 不同集合图示：

• 森林图示：

由上图对比可知，若干个互不相交的子集 相当于 森林中若干互不相关的子树。

因此：将同一子集的各个元素组织为一棵树，那么不同的子树就构成了森林，那么不同的子集就构成了森林

这样的好处：在实现 并 与 查 功能时，变成了对树的操作，理解形象。

因此对查和并的理解变化为：

• 查：从两个结点元素出发，一直向上找其根节点，若根节点相同，则属于同一个集合；反之属于不同集合。

• 并：让一棵树作为另一棵树的子树。

---

2、存储结构使用：双亲表示法

因为双亲表示法可以直接找到结点的双亲，数组S[]中存储的是对应位置元素的双亲结点的下标。

即：S[x] = t ===》结点x的双亲结点的下标为t。

并且只需要一个一维数组(S[])就能表示集合关系。

数组元素的下标代表元素名，根节点的下标代表子集名，根节点的双亲结点为负数。

---

代码实现与优化

代码实现(优化前)

1、初始化并查集

# define SIZE 50
int UFSets[SIZE]; // 集合元素数组

// 1.初始化并查集 :初始化为 -1，因为根节点为-1
void init(int S[]){
    for (int i = 0; i < SIZE; ++i) {
        S[i] = -1;
    }
}
1
2
3
4
5
6
7
8
9

2、查（Find）

// 2. Find：查操作，一直向上，找到元素x所属集合
int Find(int S[],int x){
    // 即：循环寻找x的根,找到根节点就结束
    while (S[x] >= 0){
        x = S[x];
    }
    return x;
}
1
2
3
4
5
6
7
8

3、并（Union）

// 3. Union “并”操作，将两个集合合并为一个
// 思路：①首先看两者是否已经为同一集合
//      ②由于使用双亲表示法，因此直接将一根连接到另一根下面
void Union(int S[],int Root1,int Root2){
    if(Root1 == Root2) return; // 属于同一集合就直接返回
    S[Root1] = Root2; // 将根2连接到根1下边(可以理解为树的合并)
}
1
2
3
4
5
6
7

优化1：Union的优化

1、时间复杂度分析：

并：O(1)

查：O(n) <— 最坏情况

可以看到，查操作的时间复杂度与树高密切相关。

而由于并操作的粗暴性，导致树高不受控，最终查操作的复杂度也是比较高的。

因此就有了如下的优化思路：

​ 每次Union合并时，尽可能不让树长高。

---

2、具体的优化方法：小树合并到大树

1. 用根节点的绝对值来记录树中的结点数，据此来判断树的大小。

---

3、优化后代码：

// 优化后Union
void UnionPlus(int S[],int Root1,int Root2){
    // 1.属于同一集合就直接返回
    if(Root1 == Root2) return;

    // 2.比较两树的高
    int height1 = abs(Root1);
    int height2 = abs(Root2);
    if(height1 > height2){
        // 2.1 如果树1结点数更多、更高，就将树2并到树1
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }else{
        // 反之就将树1并到树2
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以看到：

• 1.优化后Union的复杂度不变，仍为O(1)，而Find的复杂度变为O(logn)

• 2.构造的树高不超过 ⌊logn⌋+1

  因为：n个结点的完全二叉树的高度为 ⌊ logn ⌋+1。

---

优化2：Find的优化 — 压缩路径

优化1中，是通过调整并(Union)操作，来降低查(Find)操作的复杂度。

那么这次优化中，就通过调整 查(Find)操作，优化它本身。

1、回顾一下原始Find：

在这个操作中，x每一次都会找到自己的父结点，依次迭代，直到找到其根节点。

那么其实在每一次查x时，都要进行这样的全局迭代操作，代价还是挺大的。

那既然目标是找到其根(root)，那么不如直接将x的根作为x的父结点，也就是将x直接挂载到根节点下。

那么再考虑一件事：x找根的这条路上，经历过的一切结点，其根不都是x的根节点嘛。

---

2、基于这两点考虑，就有了压缩路径的思路：

一边Find，一边进行压缩路径。

上边图解可以看出，将路径上的结点直接挂载到根节点之下。这样在下次Find时，查找时间大大减少。

代码：

// 优化后Find
int FindPlus(int S[],int x){
    int root = x;
    // 1.循环找到x的根
    while(S[root] >= 0) root = S[root];

    // 2.压缩路径:将x寻根路径上所有的结点，都直接指向根节点(root)
    while(x!=root){
        int temp = S[x]; // temp指向x的父节点
        S[x] = root;  // 将x直接挂载到根节点之下
        x = temp; // 继续向上操作，将x的Find路径上的所有结点，全部直接指向根节点root
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

代码实现(优化后)：

1、初始化并查集

# define SIZE 50
int UFSets[SIZE]; // 集合元素数组

// 1.初始化并查集 :初始化为 -1，因为根节点为-1
void init(int S[]){
    for (int i = 0; i < SIZE; ++i) {
        S[i] = -1;
    }
}
1
2
3
4
5
6
7
8
9

2、查（Find）

// 优化后Find
int FindPlus(int S[],int x){
    int root = x;
    // 1.循环找到x的根
    while(S[root] >= 0) root = S[root];

    // 2.压缩路径:将x寻根路径上所有的结点，都直接指向根节点(root)
    while(x!=root){
        int temp = S[x]; // temp指向x的父节点
        S[x] = root;  // 将x直接挂载到根节点之下
        x = temp; // 继续向上操作，将x的Find路径上的所有结点，全部直接指向根节点root
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、并（Union）

// 优化后Union
void UnionPlus(int S[],int Root1,int Root2){
    // 1.属于同一集合就直接返回
    if(Root1 == Root2) return;

    // 2.比较两树的高
    int height1 = abs(Root1);
    int height2 = abs(Root2);
    if(height1 > height2){
        // 2.1 如果树1结点数更多、更高，就将树2并到树1
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }else{
        // 反之就将树1并到树2
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

并查集优化总结：

将n个独立元素Union为一个集合，要经过(n-1)次Union。