树的应用——并查集

谁借莪１个温暖的怀抱￠ 2022-11-09 12:40 167阅读 0赞

**首先，什么是并查集？**

并查集是一种简单的集合表示。

我们可以简单的思考一下这个名字，“集”应该就是集合的意思，而“并”和“查”，估计是两种动作或者形容。这个我们后面慢慢就知道了。  
![在这里插入图片描述][20210315105601419.png]

一个结合中有若干个元素，我们通常将该集合划分成若干个子集。

**我们通常用树的双亲表示法，作为并查集的存储结构。**

![在这里插入图片描述][20210315105714654.png]  
我们一般将每个子集，表示成树的形式。这些树组成了该并查集的森林。

**双亲表示法**中，我们用每个孩子结点的指针指向双亲结点，来表示其中的逻辑结构。  
通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。

> 我们也会使用该负数的绝对值，来表示该树中结点的数量。

**一些常见的方法：**

**`Initial(S)`:**  
将集合S中的每个元素都初始化为只有一个单元素的子集合。

> 就是将有n个元素的集合，初始化为n个单元素的子集合。

**`Union(S, Root1, Root2)`：**  
把集合S中的子集合（互不相交）Root2并入子集合Root1。

> 这就是所谓的“并”的操作。  
> 这里要注意的是两个集合是不想交的，如果它们有相交的部分，就不予执行。

**`Find(S, x)`：**  
查找集合S中单元素x所在的子集合，并返回该子集合的名字。

> 这就是所谓的“查”的操作。  
> 返回的就是根结点的标号。

**举例：**

我们有一个集合，S：

S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

首先进行初始化操作，`Initial(S)`：  
得到：

S0 = {0}，
    S1 = {1}，
    S2 = {2}，
    S3 = {3}，
    S4 = {4}，
    S5 = {5}，
    S6 = {6}，
    S7 = {7}，
    S8 = {8}，
    S9 = {9}

我们用树来表示的话，就是十个结点：  
![在这里插入图片描述][20210315111014776.png]  
而它们的存储，就是这样的：  
![在这里插入图片描述][20210315111037258.png]  
如果它们变成了三个子集合：

S0 = {0, 6, 7, 8},
    S1 = {1, 4, 9},
    S2 = {2, 3, 5}

这个时候，树的结构就会变为：  
![在这里插入图片描述][20210315111303718.png]  
而存储结构为：  
![在这里插入图片描述][20210315111320563.png]

**语言实现：**

#define SIZE 100
    int UFSets[SIZE];
    
    void Initial(int S[]){ 
    	for(int i = 0; i < size; i++){ 
    		S[i] = -1;
    	}
    }
    
    void Find(int S[], int x){ 
    	while(S[x] > 0){ 
    		x = S[X];
    	}
    	return x;
    }
    
    void Union(int S[], int Root1, int Root2){ 
    	S[Root2] = Root1;
    }

[20210315105601419.png]: /images/20221023/37df0d85ea8b4f47b480452086ffb518.png
[20210315105714654.png]: /images/20221023/510bd35e9ffb41029c8c4f3cf91669ae.png
[20210315111014776.png]: /images/20221023/3e8ddfc0b9694b45a2f466d6284f7917.png
[20210315111037258.png]: /images/20221023/21aa7d6c3cac4fcf89ad3af1527b84d9.png
[20210315111303718.png]: /images/20221023/5dae137d500d453b8354364de9bcad7e.png
[20210315111320563.png]: /images/20221023/22fded9180f5496b8a0bfd7c2ff0f81d.png