【数据结构】C语言实现并查集：双亲指针映射与动态连通性实现详解

蒙奇D索隆

发布于 2025-03-29 10:36:19

5000

代码可运行

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

运行总次数：0

代码可运行

导读

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

在上一篇内容中我们从数据结构的三要素初步认识了并查集这种数据结构，但是上一篇对并查集的介绍并不准确。

那我们对并查集的认识存在哪些错误呢？我们又应该如何实现并查集呢？在今天的内容中，我们将会从数据结构的三要素出发，进一步学习并实现并查集。

一、并查集的定义

并查集是一种高效管理不相交集合的数据结构，专门解决动态连通性问题。它通过树形结构组织集合元素，支持以下核心操作：

查询（Find）：判断两个元素是否属于同一集合
合并（Union）：将两个不相交的集合合并为一个集合

1.1 定义解析

并查集是一种高效管理不相交集合的数据结构

从第一句话的前部分中，我们需要提取3个关键信息：

高效管理
不相交集合
数据结构

在上一篇内容中，我们认识了并查集是一种数据结构，其逻辑结构是集合，但是为什么说并查集是高效管理呢？

这是因为在实际的使用过程中，我们通过对并查集实现优化后能够做到近似常数级的时间复杂度。具体如何实现，后面我们会继续介绍，这里先不展开。

这里说的高效管理不相交集合实际上是指并查集中各个不相交的子集。

专门解决动态连通性问题

在第一句话的后半部分中，我们需要理解什么是动态连通性问题。

简单来说，就是查询两个元素是否连通，对两个不联通的元素建立连通关系。这也就是我们所说的查找与合并。

通过树形结构组织集合元素

这里所说的树形结构与传统的树形结构是有区别的：

传统的树形结构就是我们前面学的递归结构，每一个结点都会通过其孩子指针指向孩子结点
并查集中子集的树形结构并不属于递归结构，它是由每个结点的双亲指针指向该结点的父结点

现在我们从定义出发，对并查集做出了一个更详细的介绍，下面我们继续来看一下并查集这种数据结构的三要素。

二、逻辑结构

并查集在逻辑上是由各棵不相交的子集组成的集合，子集中的元素在逻辑上呈现树形结构，每棵树的根结点作为子集的代表元素。

三、存储结构

在上一篇内容中，我们介绍了两种并查集的存储结构——顺序存储和链式存储。

但是上一篇的介绍是基于我们对并查集的初步理解而实现的，因此上一篇中提到的两种存储方式显然不能更加准确的表示并查集。

那对于并查集这个数据结构，我们又应该使用怎样的存储结构呢？下面我们就来分析一下；

3.1 树与森林的存储结构

在树与森林中，常用的存储结构有3种：

双亲表示法：通过顺序存储实现，每个结点中存放结点数据信息与双亲位置信息；

//双亲表示法
typedef struct ParentNode {
	ElemType data;	// 数据域
	int parent;		// 双亲域
}PNode;//双亲结点
typedef struct Parent {
	PNode* list;//通过顺序表实现
	int n;//结点数量
}PTree;//双亲树

孩子表示法：通过顺序表+链表实现，每个结点中存放结点数据与指向孩子链表的指针，孩子链表中存放孩子的位置信息；

//孩子表示法
typedef struct ChildNode {
	int pi;//孩子位置信息
	struct ChildNode* next_child;//孩子指针
}CNode;//孩子结点
typedef struct ParentNode {
	ElemType data;//结点数据域
	CNode* child;//孩子指针域
}PN;//双亲结点
typedef struct ChildTree {
	PN* list;//顺序表
	int n;//结点数量
}CTree;//孩子树

孩子兄弟表示法：通过二叉链表实现，每个结点中存放结点数据与指向孩子的左孩子指针以及指向兄弟的右兄弟指针；

//孩子兄弟表示法
typedef struct ChildBrotherNode {
	ElemType data;//数据域
	struct ChildBroherNode* lchild, * rbrother;//左孩子、右兄弟指针域
}CBNode, * CBTree;//孩子兄弟结点、孩子兄弟树

3.2 并查集的存储结构

在并查集中，元素是自下而上的方式组成的一棵树，这种形态与树的双亲表示法一致，都是通过孩子找双亲。因此双亲表示法更符合并查集。

因此我们可以借助双亲表示法来作为并查集的存储结构，每个结点会存放两个信息——结点数据以及双亲位置信息：

//顺序存储
typedef struct DSUNode {
	ElemType data;//数据域
	int parent;//双亲位置信息
}DSUNode;//并查集结点
typedef struct DSU {
	DSUNode* list;//顺序表
	int len;//表长
}DSU;//并查集

四、算法

在并查集中，支持3种操作：

Initial(S)：将集合S中的每个元素都初始化为只有一个单元素的子集合；
Find(S,x)：查找集合S中元素x所在子集，并返回子集的根结点；
Union(S,Root1,Root2)：将集合S中不相交的子集Root1与Root2进行合并；

那也就是说，我们不会对并查集中的元素进行任何的添加与修改的问题，因此我们能否认为并查集实际上就是一个映射表，通过并查集这个映射表来实现对元素的查找与逻辑上的合并。

可能有朋友不理解我想表达的是什么意思，下面我们就来对这个观点进行说明。

首先并查集中的元素是在逻辑上呈现自下而上的树形结构，并不是物理上的自下而上，因此我们可以认为并查集中的元素在物理上并没有限制；

其次，通过并查集的双亲指针的指向，我们实现了将物理上无限制的元素，在逻辑上进行了连接，也就是通过并查集，指示了各个结点之间的关系，对元素本身并没有任何改变；

最后，在并查集中，我们是对元素所在的集合进行查找，对两个不相交的子集进行合并，也就是说我仅通过双亲指针即可实现全部操作。

因此在实际的使用过程中，我们并不需要关心元素的数据信息，只需要关系该元素的双亲指针，那么我们不妨通过创建一个元素与双亲指针的映射关系来实现对指定元素的查找与合并即可。

如对于小写字母而言，我们可以采用长度为26的字符数组，通过数组下标与'a'~'z'进行一一对应，数组中存放该元素的双亲位置信息，这样我们就能通过这种映射关系快速的找到指定元素所在集合，如下所示：

//顺序存储
typedef struct DSU {
	char parent[26];//双亲位置信息
}DSU;//并查集
//元素与下标之间的映射关系
int GetKey(char x) {
	return x - 'a';
}

在这种思路下，那么我们对查找与合并的实现就很简单了：

查找：通过指定元素与下标的映射关系，找到其双亲的位置信息，通过该位置信息一路向上找到根结点；
合并：通过指定元素与喜爱宝的映射关系，找到其所在子集的根结点：
- 若根结点相同，则表明双方位于同一个子集，不执行任何操作；
- 若根结点不同，则通过修改根结点的双亲位置信息来实现子集的合并；

理解了这种映射思路，那我们就可以通过C语言来实现并查集了；

五、基本实现

在具体的实现中，我们以字符元素为例，简单一点，我们就直接采用小写字母为例进行实现。

5.1 初始化

小写字符总共有26个，因此并查集的最大长度也是26个。这里我们直接创建一个长度为26的字符数组，并将数组中的元素初始化为-1，表示该数组中的元素全部为独立的子集：

#define MAXSIZE 26

void Initial(DSU* s) {
	assert(s);
	for (int i = 0; i < MAXSIZE; i++) {
		s->parent[i] = -1;//将元素初始化为单个子集
	}
	printf("完成初始化\n");
}

5.2 查找

查找操作是查找该元素所在的子集，而并查集中，每棵子树的根结点作为该子集的代表元素，因此查找某个元素所在子集，实际上就是查找该元素的所在子集的根节点。

这里我们以双亲指针为-1代表该结点为根结点，因此我们只需要根据双亲指针查找到值为-1的根结点即可：

//元素与下标之间的映射关系
int GetKey(char x) {
	return x - 'a';
}
//查找
int Find(DSU* s, char x) {
	int key = GetKey(x);//获取该元素所映射的双亲指针下标
	while (s->parent[key] != -1) {
		key = s->parent[key];//自下而上查找根结点
	}
	return key;//返回根结点所映射的下标
}

5.3 合并

并查集的合并操作是将两个不相交的子集进行合并，如果，此时的两个子集相等，我们则不需要执行任何操作，如果不相等，我们只需要将其中一个子集的双亲指针指向另一个子集的根结点即可：

//合并
void Union(DSU* s, int root1, int root2) {
	if (root1 != root2) {
		s->parent[root1] = root2;
		printf("完成合并\n");
		return;
	}
	printf("合并对象为同一个子集，无法合并\n");
}