数据结构考研笔记（十二）——树的应用（并查集）

冷不防 2022-12-16 05:58 120阅读 0赞

# 并查集 #

并查集：一种简单的集合表示。  
通常用树的**双亲**表示法作为并查集的存储结构。  
通常用数组元素的下标代表**元素名**，用根结点的下标代表子**集合名**，根结点的双亲结点为**负数**。

Initial(S)
    将集合S中的每个元素都初始化为只有一个单元素的子集合。
    Union(S, Root1, Root2)
    把集合S中的子集合(互不相交) Root2并入子集合Root1.
    Find(S, x)
    查找集合S中单元素x所在子集合，并返回该子集合的名字。

下面的结点都是根节点，所以双亲结点都是负数  
S=\{0,1,2,3,4,5,6,7,8,9\}  
S0=\{0\}, S1= \{1\}, S2 = \{2\}, S3 = \{3\}, S4= \{4\},  
S5= \{5\}, S6= \{6\}, S7 = \{7\}, S8= \{8\}, S9 = \{9\}  
![在这里插入图片描述][20201018210852708.png_pic_center]  
**例题：**

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

解析：S0是根节点，下面有四个子结点（0，6，7，8）所以为 -4 ， S1和S2 是根节点下面有三个子结点所以为-3， S4、S5、S6、S7、S8、S9都是子结点所以parent填相应的双亲结点,如S4的双亲结点是s1，表就填1。如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]

#define SIZE 100
    int UFSets [SIZE] ;//双亲结点下标
    void Initial (int S[]) {
        //初始化
    	for(int i=0; i<size; i++)
    		S[i]=-1;
    }
    //查找
    int 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 ;
    }

[20201018210852708.png_pic_center]: /images/20221123/b402e86627334848a1221169bc6387b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6fef08c2923f4c658f6834c400811d46.png