ddddfang's Blog.

union-find-set

并查集
字数统计: 1.2k阅读时长: 5 min
2019/03/19 Share

用于归类，判断动态连通性的一种概念。比如下面 0-9 个点，归并(4,3)即认为 4和3 同组（或者连通）。一波 归并 操作之后，查看某两个点是否连通（同组）。
http://blog.jobbole.com/108359/

并查集

实现思路：
1、我们可以给每个元素设定一个 group_id 变量，指示自己所属的组。每当归并两个元素（A 和 B，group_id 分别为 group_id1 和 group_id2）的时候，遍历查询，吧所有group_id1全部改成group_id2（或者全部把group_id2 改成 group_id1，等价）。但是这样效率成为问题。每次归并两个group的时候复杂度都是O(N)
2、思路1之所以复杂度为O(N)，原因在于每个元素都自己维护一份group_id（直观上大部分人都会这么实现），我们可以使用 link 的思想，仍然在初始化的时候为每个元素指派一个 唯一的group_id，但是在归并 A和B 的时候，让A的 group_id1 变成B元素的index（即让A的 group_id 指向B）。这样只维护了一份 group_id，理论上归并两个组应该会比较快，理想情况O(lgN)（最差也是O(N)）。但是在查找A所属的 group 的时候慢啦（理想上也是O(lgN)，最差O(N)），思路1在查找某个元素所属组的时候可是O(1)呀。改进：引入了所谓树高度的概念（好像叫秩），就是在思路1里 “group_id1全部改成group_id2还是group_id2全部改成group_id1”这个问题没有那么随便了，秩小的组插入到秩大的组里面，使得每次查找可以趋近于O(lgN)（不然最坏可能是O(N)。。。）
3、路径压缩。第一次查找的时候O(lgN)，查找到之后，直接将自己的 group_id 指向 本组掌门人（即那个 group_id 为自身 的元素），这样下次再次查找的时候可认为是O(1)了。

group_id 理论上可以是任何值，讨论的时候直接就给了元素本身的值（默认每个元素都是不一样的哈）。当为一个节点的时候，可以使用本节点的指针即 address 作为 group_id 。貌似后者应用型更强啊，所以下面我写的这个例子是后者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//uFindSet.h
#ifndef _U_FIND_SET
#define _U_FIND_SET


typedef struct
{
    int s32Data;
    unsigned long s32GroupId;
}stNode;

void createNode(stNode **ppNode,int data);
void destroyNode(stNode *pNode);
unsigned long findGroupId(stNode *pNode);
void unionNode(stNode *x,stNode *y);
int getGroupCnt();

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//uFindSet.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "uFindSet.h"

static int group_count=0;

//==============================================================
void createNode(stNode **ppNode,int data)
{
    stNode *p = NULL;
    if(!ppNode)
        return;
    *ppNode = NULL;
    p = (stNode *)malloc(sizeof(stNode));
    if(!p)
        return;
    p->s32Data = data;
    p->s32GroupId = (unsigned long)p;    //每个元素的 组 都是自己,各不一样
    *ppNode = p;
    group_count++;
}

void initNode(stNode *pNode,int data)
{
    if(!pNode)
        return;
    pNode->s32Data = data;
    pNode->s32GroupId = (unsigned long)pNode;
    group_count++;
}

void destroyNode(stNode *pNode)
{
    if(!pNode)
        return;
    free(pNode);
}

unsigned long findGroupId(stNode *pNode)
{
    if(!pNode)
        return -1;
    if( pNode->s32GroupId != (unsigned long)pNode )
    {
        //递归返回的过程会将 group_id 直接指向"组 即自己"的那个元素,下次查找就是O(1)
        pNode->s32GroupId = findGroupId((stNode *)(pNode->s32GroupId));
    }
    return pNode->s32GroupId;
}

/*
//查找元素所属的 组(非递归)
//这么实现没准还真的不如递归实现的好,因为你没有使用栈,导致你压缩的只是查找起点的
//那个元素的 group_id,而上面的递归则是路径上的所有元素都同时被压缩!
unsigned long findGroupId(stNode *pNode)
{
    stNode *tmp = pNode;    //用 tmp 去找掌门人
    if(!pNode)
        return -1;
    while( tmp->s32GroupId != (unsigned long)tmp )
    {
        tmp = (stNode *)(tmp->s32GroupId);
    }
    pNode->s32GroupId = (unsigned long)tmp;
    return pNode->s32GroupId;
}*/

//将x的组id变成了y
void unionNode(stNode *x,stNode *y)
{
    unsigned long g_x = findGroupId(x);
    unsigned long g_y = findGroupId(y);
    if(g_x != g_y)
    {
        //x->s32GroupId = y->s32GroupId;
        ((stNode *)g_x)->s32GroupId = g_y;
        group_count--;
    }
}

int getGroupCnt()
{
    return group_count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//并查集测试
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "uFindSet.h"

#define U_FIND_SET_NUM 10000

//==============================================================

int uFindSet_test()
{
    int i;
    stNode *abc[U_FIND_SET_NUM]={0};
    srand(0); //生成随机种子

    printf(" init group id \n");
    for(i=0;i<U_FIND_SET_NUM;i++)
    {
        createNode(&abc[i],i);
    }

    printf(" elem and their group\n");
    for(i=0;i<U_FIND_SET_NUM;i++)
    {
        unsigned long tmpid = findGroupId(abc[i]);
        printf("<init>element %d, group_id is %lu(%d))\n",i,tmpid,((stNode *)tmpid)->s32Data );
    }

    printf(" union some data randomly\n");
    for(i=0;i<U_FIND_SET_NUM;i++)
    {
        int a = rand()%U_FIND_SET_NUM;
        int b = rand()%U_FIND_SET_NUM;
        printf("union %d and %d\n",a,b);
        unionNode(abc[a],abc[b]);
    }
    printf(" elem and their group \n");
    for(i=0;i<U_FIND_SET_NUM;i++)
    {
        unsigned long tmpid = findGroupId(abc[i]);
        printf("<after>element %d, group_id is %lu(%d))\n",i,tmpid,((stNode *)tmpid)->s32Data );
    }
    printf("group_count %d\n",getGroupCnt());

    for(i=0;i<U_FIND_SET_NUM;i++)
    {
        destroyNode(abc[i]);
        abc[i] = NULL;
    }
    return 0;
}

原文作者：ddddfang

原文链接：https://ddddfang.github.io/2019/03/19/union-find-set/

发表日期：March 19th 2019, 6:37:25 pm

更新日期：March 19th 2019, 6:42:53 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 42
2019
binary-search bitmap caffe c++ 单例模式 common misc makefile 宏 顺序容器 智能指针 排序 shell linux command docker blog ffmpeg gdb gitbook p4 printf 可变参数 static and dynamic library 第k小的数 ubuntu setup 并查集 git draw.io markdown vscode office2016 密钥 键值对集合 链表 最大堆(大顶堆) swig python c vim 红黑树 skip-list hash-table
algorithm-and-data-struct caffe common-misc cpp linux-daily ffmpeg