一种树形结构——并查集

发表于 分类于

概述

并查集（Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。根据并查集的名字可以很直观的理解它的意思，即“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。
有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作： * Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 * Union：将两个子集合并成同一个集合。

适用问题

并查集用在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。 ## 图联通问题 * 维护无向图的连通性。支持判断两个点是否在同一连通块内。 * 判断增加一条边是否会产生环：用在求解最小生成树的Kruskal算法里。 ## 亲戚关系 判断亲戚关系是一个典型的并查集问题，一个大家族的成员很多，判断两个成员是否为亲戚是比较困难的。我们可以建立模型，把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。因此，这里就可以考虑用并查集进行维护了。

并查集基本操作

初始化集合

并查集首先得制作一个集合，初始化时一般将元素本身的索引作为其的值，即将元素的父节点设置为它自己。这能保证其独一性，即每个元素在不同的集合中。 

1
2
3
4
5
6
7
8
# 初始化
int init(int n)
{
    int fa[n];
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
        return fa
}
## 查询 查询操作即为寻找元素最根本的父节点(根节点)。可以采用递归的形式来查找，当元素的索引与其值不相等时，说明元素存在父节点；当他们相等的时候说明元素的父节点为其本身，即为根节点。 
1
2
3
4
5
6
7
int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

合并

合并操作也是很简单的，只需将其中一个元素的根节点指向另外一个元素就可以了。两者的指向顺序暂不讨论。后续会给出一种路径压缩算法来指定合并的顺序以达到最高效率。 

1
2
3
4
5
6
7
8
void merge(int x,int y){
        int root_x = find(x);
        int root_y = find(y);
        
        if(root_x != root_y){
            father[root_x] = root_y;
        }
    }
## 连通性判断 直接判断两个元素的根节点是否相同即可判断两个元素是否在同一个集合内，即他们是否连通。 
1
2
3
bool is_connected(int x,int y){
       return find(x) == find(y);
   }
## 路径压缩 通过上面的操作，已经可以制作了一个简单的并查集了，但是这种简单的并查集的效率一般不是很高。我们在进行合并的时候，由于一个集合的根父节点指定的位置可以是另一个集合的任意位置，在合并的过程中，集合的关系链可能会越来越长，这样在查找根节点的时候可能需要递归很多次，大大影响了效率。所以需要一种方式来避免“长链”的出现。 ### 合并（路径压缩） 我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。递归的写法如下，与普通的查找根节点算法相比，多了一步设置父节点为根节点的步骤。 
1
2
3
4
5
6
7
8
9
int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}
### 按秩合并 我们用一个数组 rank[] 记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用，时间复杂度接近O(n) ，但是很可能会破坏rank的准确性。值得注意的是，按秩合并会带来额外的空间复杂度。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

应用例程

题目描述

省份的数量(Leetcode.547)
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中省份的数量。

示例1：
输入： isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出： 2
对角线上的元素为其本身，一定联通，恒为1.矩阵中1与2城市联通，所以1、2构成一个省份，3单独作为一个省份，省份数量为2.

示例2：
输入： isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出： 3
对角矩阵，表示无城市联通，所以三个城市均可单独作为一个省份，总省份数量为3.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def find(index: int) -> int: #查找根节点
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int): #合并两个(城市)集合
            parent[find(index1)] = find(index2)
        
        provinces = len(isConnected) #定义初始省份数量
        parent = list(range(provinces)) #每个城市作为一个省份
        
        for i in range(provinces):
            for j in range(i + 1, provinces):
                if isConnected[i][j] == 1: #如果相应城市联通，将他们加入同一个集合。
                    union(i, j)
        
        circles = sum(parent[i] == i for i in range(provinces)) #统计整个父矩阵中父节点为自己的数量(根节点数量)，也就是集合数量、省份数量
        return circles