不相交集 / 并查集（C语言实现）

本文主要是介绍不相交集 / 并查集（C语言实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

两个等价类集合Si和Sj如果满足：Si和Sj的交集为空集，则称Si和Sj构成一个不相交集。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。

下面我们用数组存储森林，从而实现并查集。

代码如下：

DisjSet.h

#ifndef DisjSet_DisjSet_h
#define DisjSet_DisjSet_hconst int NumSets = 10;/** Disjoint Set 不相交集 / 并查集* 主要操作为：查找和合并*/
typedef int DisjSet[NumSets + 1]; // 为了下标对齐，这里设定数组大小为NumSets + 1，第0个元素起占位作用
typedef int SetType; // 父节点保存的元素的类型
typedef int ElementType;// 初始化
void initialize(DisjSet set);// （按树的大小）合并两个不相交集，root1和root2分别表示两棵要合并的树的根
void setUnion(DisjSet set, SetType root1, SetType root2);// 查找x属于set中的哪个不相交集
SetType find(ElementType x, DisjSet set);#endif

DisjSet.c

#include <stdio.h>
#include <stdlib.h>
#include "DisjSet.h"void
initialize(DisjSet set)
{/** 初始化时，每个根节点中保存的值就是该树的大小的负值，也就是-1* 在这里，树的大小的意思是树中有多少个节点* 如果节点中保存的值为正数，那么该值表示父节点在数组中的下标** 注意：* 数组的下标就是节点中保存的元素* 数组中的元素表示父节点中保存的元素或树的大小的负值*/for (int i = NumSets; i > 0; i--)set[i] = -1;// do nothing with set[0]
}/** 按树的大小求并：较小的树成为较大的树的子树*/
void
setUnion(DisjSet set, SetType root1, SetType root2)
{if (set[root1] >= 0 || set[root2] >= 0)printf("Fail to union: Root1 and Root2 is not a root of tree");if (set[root1] == set[root2]) // 同一棵树return;else{if (set[root1] > set[root2]) // -set[root1] < -set[root2]set[root1] = root2;else // -set[root1] > -set[root2]set[root2] = root1;}
}SetType
find(ElementType x, DisjSet set)
{if (x > NumSets){printf("x is not in DisjSet");return 0;}if (set[x] == 0) // 空树或该节点指向占位的第0个数组元素，因此出错{printf("Error: set[x] can not be 0");return 0;}/** 在查找到某个元素后，执行路径压缩算法* 注意：路径压缩算法和按大小合并算法兼容，和按树高度合并算法不兼容*/if (set[x] < 0)return x;elsereturn set[x] = find(set[x], set); // 沿上查找根节点，并设为x的父节点
}

主要参考了Mark Allen Weiss的《数据结构与算法分析 —— C语言描述》。

这篇关于不相交集 / 并查集（C语言实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---