【数据结构】数据结构高手进阶：并查集VS森林，谁才是集合操作的真神？

并查集

【数据结构】数据结构高手进阶：并查集VS森林，谁才是集合操作的真神？_并查集

导读

大家好，很高兴又和大家见面啦！！！

在数据的逻辑结构中，可以分为两大类：

• 线性结构
• 非线性结构

在线性结构中，我们已经学习了一系列的数据结构：

• 一般线性表
• 顺序表
• 链表
• 受限线性表
• 栈
• 队列
• 串
• 数组与特殊矩阵

在非线性结构中，总共有3种非线性结构：

• 集合
• 树形结构
• 图状结构

其中我们已经学习了树形结构中的相关数据结构：

• 树
• 森林
• 二叉树
• 二叉线索树
• 哈夫曼树

从今天的内容开始，我们将会进入另外两种非线性结构的学习。

今天我们会学习第二种非线性结构——集合。下面我们就直接进入今天的内容吧！！！

一、 集合

集合这种逻辑结构是指在集合中的数据元素之间除了同一个集合外，没有其它的关系，如下图所示：

【数据结构】数据结构高手进阶：并查集VS森林，谁才是集合操作的真神？_顺序存储_02

在上图中，我们展示了4种集合，可以看到集合中的元素之间并无任何关系，它们仅仅就是因为满足某种条件而位于同一个集合之中。

从上图我们也不难发现各个集合之间也是互不相交的，因此当这些集合作为元素也存在于一个更大的集合中时，这些集合就变成了更大集合的子集：

【数据结构】数据结构高手进阶：并查集VS森林，谁才是集合操作的真神？_顺序存储_03

在上图中，我们就将刚才的四个集合又合并成了两个大的集合，此时刚才的集合就变成了各自大集合中的子集。

在大集合中，子集之间也是互不相交，大集合中的元素之间此时会存在两种关系：

• 在同一个子集中
• 在不同的子集中

除了这两种关系之外，元素之间再无其它关系。

了解了集合这种逻辑结构后，下面我们就来看一下并查集；

二、 并查集

并查集（Disjoint Set Union，DSU）是一种数据结构。

既然要学习数据结构，那么数据结构的三要素我们是一定得了解的。

2.1 逻辑结构

在并查集中，各元素之间呈现的是一种集合关系，即：

• 各个数据元素在逻辑上只是存在于该集合中，并无其它联系

在前面的学习中我们就有学习过森林是多棵互不相交的树组成的集合。从集合的角度来看，树与树之间只存在一种关系：

• 各棵树只存在于该森林中，彼此之间不存在任何关系

那也就是是说，并查集和森林类似，并查集也是由多棵树组成的森林，每棵树表示一个子集，树根为子集的代表元素。

2.2 存储结构

对于集合中的数据而言，我们只需要搞清楚一个问题：

• 该数据所在的是什么集合

那么我们在进行数据的存储时，只需要解决这个问题即可。

在之前我们学过数据结构的存储结构有四种：

• 顺序存储
• 链式存储
• 索引存储
• 散列存储

前面我们学习的数据结构，从线性表到树，我们在实现其存储结构时都是通过顺序存储和链式存储进行实现的，在并查集中，我们同样可以采用这两种方式实现。

2.2.1 顺序存储

顺序存储就是通过申请一块连续的空间来存储数据，数据与数据之间在物理位置上相邻，在逻辑上也相邻。

这种存储方式对并查集中的元素而言是没有任何影响的，因为并查集中的元素只需要关注它是否在当前的集合中，它与其它元素在物理位置上是否相邻，在逻辑上是否相邻这并不重要。

因此当我们进行顺序存储的方式实现并查集时，我们只需要能够将元素与集合的关系表示清楚即可！！！

那下面问题来了，我们如何来表示元素与集合之间的关系呢？

这里我们需要结合前面的所学来解决这个问题；

在线性表中，我们要表示元素之间的关系，我们可以通过指针的指向来实现：

• 顺序表：元素与元素之间通过下标这个伪指针实现了其逻辑上的一对一；
• 链表：元素与元素之间通过结点指针实现了其逻辑上的一对一；

在树中，各结点之间的关系，结点与树的关系我们同样通过指针来实现，这里我们以二叉树为例，在二叉树中：

• 顺序存储：元素与元素之间通过其下标这个伪指针之间的关系实现了其逻辑上的一对多；
• 链式存储：结点与结点之间通过其左右孩子指针实现了其逻辑上的一对多；

从这个思路来看，当我们要通过顺序存储的方式来实现并查集的话，我们同样可以通过下标这个伪指针来指明元素所在的集合；

此时这个集合名就相当于是线性表中的表头，树中的根结点。既然这样，那我们不妨在结点中通过数据域来记录数据，通过指针域来记录所在集合信息，如下所示：

【数据结构】数据结构高手进阶：并查集VS森林，谁才是集合操作的真神？_并查集_04

这里我们将结点A作为集合的根结点，其它结点通过伪指针指向A来表明该元素与A位于同一个集合中。如果用C语言来描述结点结构的话，则是：

代码语言：javascript代码运行次数：0运行复制

//顺序存储
typedef struct DSUNode {
	ElemType data;//数据域
	int union_pi;//集合指针
}DSUNode;
//DSUNode——并查集结点
typedef struct DSU {
	DSUNode* list;//线性表
	int n;//结点数量
}DSU;
//DSU——并查集

有没有觉得很眼熟？没错这个结点结构与树的双亲表示法是一致的。

在树的双亲表示法中，我们通过记录孩子的信息以及伪指针域记录双亲的位置从而实现通过孩子找双亲；

在并查集中，如果我们要判断该结点是否属于某个集合，那是不是就相当于通过孩子向上找到自己的双亲呢？

因此我们树的双亲表示法与并查集的顺序存储的实现是一致的。

2.2.2 链式存储

当我们采用链式存储时，我们期待的效果应该是：

【数据结构】数据结构高手进阶：并查集VS森林，谁才是集合操作的真神？_顺序存储_05

如果这样的话，就会遇到一个问题，我们应该如何存储每一个结点呢？

由于各结点之间并无任何关系，因此我们想通过结点之间的关系来找到结点显然不太合理，因此并查集无法通过链式存储的方式直接实现。

那我们可不可以采用其它的方式来模拟实现并查集呢？

从上图中我们不难看出，此时我们的难点在于对其他元素的处理，我们应该如何找到其他的元素。如果我们增加一个元素指针，用于指向集合中的其他元素，那问题是不是就解决了呢？

【数据结构】数据结构高手进阶：并查集VS森林，谁才是集合操作的真神？_结点_06

可以看到，此时当我们采用双指针时，就很好的解决了这个问题，结点A作为链表的首元素，通过它能够找到集合中的所有元素，同时所有的元素通过集合指针都能判断其是否与结点A在同一个集合中；

因此，当我们要通过链式存储的方式实现一个并查集时，我们可以通过双叉链表的方式实现，如下所示：

代码语言：javascript代码运行次数：0运行复制

//链式存储
typedef struct LinkNode {
	ElemType data;//数据域
	struct LinkNode* node;//结点指针
	struct LinkNode* union_pi;//集合指针
}LNode;
typedef struct DSULink {
	LNode* head;//链表头指针
	int n;//结点个数
}DSULink;

2.3 算法

在并查集中，个元素之间主要可以实现两种功能：

• 查找（Find(S,x)）：查找集合S中元素x所在子集，并返回子集的根结点；
• 合并（Union(S,Root1,Root2)）：将集合S中不相交的子集Root1与Root2进行合并；

如果我们没有一个并查集，那自然是无法进行上述功能的执行，因此在并查集中，我们还需要实现初始化功能：

• 初始化（Initial(S)）：将集合中的每个元素都初始化为只有一个单元素的子集；

从算法中我们可以得出一个结论：

• 并查集更适合顺序存储

在介绍顺序表与链表时我们就曾提到过一个观点：

• 顺序表更适合频繁查找的情况
• 链表更适合频繁插入与删除的情况

在并查集中，我们主要就是为了对元素进行查找，因此使用顺序存储会更合适；

三、并查集与森林

3.1 相同点

从并查集的逻辑结构、存储结构以及算法来看，它的整个内容与我们所学的森林是高度一致的：

• 逻辑结构
• 森林中的树与树之间在逻辑上呈现集合的关系
• 并查集中的元素之间在逻辑上呈现集合的关系
• 存储结构
• 森林的双亲表示法通过指向双亲结点的位置的伪指针实现从孩子结点找双亲；
• 并查集通过指向集合首元素位置的伪指针实现从元素找集合；
• 算法
• 查找
• 在森林中，我们可以查找结点x存在于哪棵树中
• 在并查集中，我们可以查找结点x存在于哪个子集中；
• 合并
• 在森林中，我们可以合并两棵不相交的树
• 在并查集中，我们可以合并两个不相交的子集

从这个对比中可以看到，似乎并查集与森林没啥区别，那是不是说并查集就是森林呢？

显然不是，下面我们就来看一下二者之间的不同点；

3.2 不同点

并查集实际上是树的一种应用，从前面的介绍中我们不难发现，当我们通过链式存储的方式来实现并查集时，每个结点都是满足树形结构的特征：

• 元素与元素之间存在一对多的关系

因此并查集实际上也是一种树形结构，但是它与树和森林还是有很大的区别的：

• 树的高度不同
• 在树和森林中，树的高度是没有任何限制的
• 在并查集中，我们不难发现，所有的结点都需要指向根结点，因此并查集中的树是高度尽可能低的树
• 算法不同
• 在树和森林中，我们主要以实现遍历、插入、删除、搜索等操作；
• 在并查集中，我们主要实现的是查找与合并等操作
• 存储方式不同
• 森林需支持动态插入/删除操作，更多使用链式存储（如孩子兄弟表示法）
• 并查集通常采用顺序存储（数组）以优化查找与合并效率；

结语

在今天的内容中我们介绍了并查集的相关概念：

• 并查集是一种集合类型的数据结构
• 并查集与森林十分相似，但又有区别
• 相同点
• 并查集的子集与子集之间的逻辑结构与森林中树与树之间的逻辑结构相同，都是集合
• 并查集中同一个子集中的元素与元素之间的逻辑结构与森林中同一棵树中的元素与元素之间的逻辑结构相同，都是树形结构
• 并查集的顺序存储结构与森林的双亲表示法相同
• 并查集可以实现的操作，森林同样可以实现
• 不同点
• 并查集中的树形结构是追求的高度尽可能低的树，而森林中的树的高度则没有任何要求
• 并查集通常采用顺序存储（数组）以优化查找与合并效率；森林因需支持动态插入/删除操作，更多使用链式存储（如孩子兄弟表示法）
• 并查集主要进行查找与合并的操作，森林主要进行遍历、插入、删除等操作

今天的内容到这里就全部结束了，在下一篇内容中我们将介绍《C语言实现并查集》，大家记得关注哦！如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以将博主的内容转发给你身边需要的朋友。最后感谢各位朋友的支持，咱们下一篇再见！！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-20，如有侵权请联系 cloudcommunity@tencent 删除前往查看数据结构集合数据指针存储