数据结构: 并查集

Posted on 2024-10-02 Edited on 2025-12-31 In Algorithm , Data Structure Word count in article: 1.3k Reading time ≈ 5 mins.

并查集

概述

并查集用于解决不相交集合的问题，高效地提供两种方法：

合并：用于将两个不相交集合合并
查询：用于查询一个元素在哪个集合里

基于上述操作，并查集这种数据结构可用于解决许多问题，例如：

查询两个元素是否在同一集合，也即用于判断两个元素是否相通
合并两个不相交元素所在集合
找出集合的总个数
找出一个集合的元素总个数

但这种结构是有局限的，不能通过它来解决诸如以下的问题：

分离集合问题，并查集中的集合只并不分，也不能删除元素
不会保存节点间的关系，只会保存集合与节点的关系；这种问题应依靠图来解决

结构与简单实现

具体结构

并查集是一种树状结构，对于一个集合，只选出一个元素作为代表元素，用它来标识一个集合；代表元素指向它自己，至于集合内的其它元素，或直接或间接地，最后都将指向这个代表元素

在没有任何优化的并查集中，并和查是这样实现的：

查：递归搜索节点的父节点，直到找到祖宗节点(指向自己的节点)，则它属于这个祖宗节点所代表的集合
并：寻找两元素的祖宗节点，让其中之一指向另外的节点即可

初始化

并查集最浅显的实现方法是普通数组，下标代表元素编号，数组存储的是元素的父节点下标，初始化时，让所有元素指向自己：

1	int fa[n] = {0,1,...,n-1};

`find()`

查询操作最简单的方法是递归(无优化)：

1
2
3

int find(int number) { // 找到祖宗节点,递归结束.
    return number == fa[number] ? number : find(fa[number]);
}

`Union()`

合并操作需要借助查询(无优化)：

1
2
3

void Union(int num_1, int num_2) {
    fa[find(num_1)] = find(num_2);
}

方法优化

路径压缩

对查询来说，由于每次合并后都将使树深度加一，故递归层数加一，则可以采取路径压缩方法，即沿途让每个元素直接指向父节点：

1
2
3

int find() {
    return fa[number] = number == fa[number] ? number : find(fa[number]);
}

这种方法有极大可能缩短搜索路径，但第一次搜索依然有可能递归多层；对于最后一个节点来说，只要一直不对它进行查询，它所在路径深度仍然较大

需要注意的是，这种优化会覆盖节点与父节点间的信息，如果实际问题中需要维护中间节点，就不应该采用这种优化方法

按秩合并

对合并来说，每次合并应该让深度小的集合指向深度大的集合，这能够使新集合的秩(即深度)不增大(否则会加一)，这种优化需要额外维护一个rank数组，该数组下标表示元素编号，只存储祖宗节点所在集合的深度(未进行路径压缩)：

int rank[n] {1,1,...,1};
void Union(int num_1, int num_2) {
    int head_1 = find(num_1), head_2 = find(num_2);
    if (rank[head_1] < rank[head_2]) {
        fa[head_1] = head_2;
        return;
    }
    else if (rank[head_1] == rank[head_2]) {
  ++rank[head_1];  // 相等时树深仍加1.
    }
    fa[head_2] = head_1; // 1树更深或深度相同,都让2树指向1树.
}

如果希望同时进行路径压缩和按秩合并优化，那么可能需要维护全局的rank防止树深的随意变化

或者更改秩的定义，在上述定义中，秩是树的绝对深度，如果要进行路径压缩：

定义秩为树深的上界
定义秩为元素个数，因为元素多的树倾向于更深，同时还能存储元素个数

所有这些定义方法都只是尝试不增加树深，不一定合并出更浅的树

管理非整型数据

上述并查集的节点数据都是基础类型的，如果需要管理其它类型，可以尝试让数组存储该类对象指针的结构体，在查询时，不采取递归而是循环的方式，返回头结点指针：

struct Struct {
    Class* me;
    int father;
};
Struct fa[n] {{&Obj0,0},{&Objn_1,n-1}};
const Class* find(int index) {
    while (index != fa[index].father) { // 较难直观地进行路径压缩,除非允许再循环一次.
        index = fa[index].father;
    }
    return fa[index].me;
}

这样的并查集编号都为整型，实际问题中很难知道一个对象的具体编号，这时可通过指针查询：

class Class { // 需要该类含有指向父节点的指针.
    Class* fa;
};
Class* find(const Class* p) {
    return p->fa = p == p->father ? p : find(p->father);
}

但实际情况中，通过整型数组与哈希表映射(键为value_type，值为整型)相结合来实现更为有效

并查集

概述