个性化阅读
专注于IT技术分析

不相交集(disjoint set)原理和实现图文详解

不相交集(disjoint set)是一种数据结构,又称为并查集(union-find set),或称为联合-查找数据结构或合并查找数据结构,该数据结构主要是使用联合-查找算法(union-find algorithm)。不相交集是一种很有用的数据结构,算法简单而高效,不相交集的应用主要体现在图(graph)中,在图中进行环检测(cycle detection),例如在Kruskal最小生成树算法中,另外也可以解决一些实际问题,例如工作序列最大利润问题。本节不相交集的内容主要还是为了下一节图(graph)数据结构作准备,它也可以独立实现一些功能。

不相交集(disjoint-set)ADT

一、不相交集的等价定义

不相交集也就是互相交集为空的集合,不相交集是一种处理关系的数据结构,特别地,这里使用元素和集合定义等价关系。存在集合S,元素x和y属于S:

  1. 在集合S上存在关系R(Relation);
  2. XRy等于true或false;
  3. 如果xRy等于true,则说x和y有关系。

等价关系比关系R稍微严格,需要满足以下性质:

  1. 自反性,所有属于S的x,xRx,也就是x和自己有关系;
  2. 对称性,xRy,当且仅当yRx,也就是x和y互相有关系;
  3. 传递性,如果xRy且yRz,则xRz,也就是x和z间接有关系。

这里说的关系是很广泛的,可以是任何关系,集合其实就是数据元素的集合,R是数据元素之间的关系。例如R为关系<=的时候不是等价关系,此时元素为一般实数,缺少对称性,a<=b时不一定b<=a。电气连通性是等价关系,元素为电气设备,一个国家的所有城市也有等价关系,元素为每个城市。

等价关系的问题是,给定一个等价关系~,对于任意的x和y,是否x~y(也就是问x和y是否有等价关系)。解决此问题的一个较好的方式是,先找出属于S的元素x的等价类Q,Q是S的一个子集,该子集包含所有与x有关系的元素,当我们要确定是否x~y时,转换为验证x和y是否在同一个等价类Q中,也就是x和y是否在同一个集合中。

我们可以使用散列方式描述集合中的元素,即Si={i},0 <= i <= n-1,初始化的时候需要创建n个集合,此时Si和Sj相交为空集,也就是不相交集。

不相交集的基本操作为make-set创建集合、find查找和union合并,下面会介绍不相交集使用路径压缩和按秩合并的优化方式,使用该方式每个操作的平均时间为O(a(n)),a(n)是阿克曼函数的反函数,a(n)在n很大的时候还是小于5,因此算法非常高效。

二、不相交集的应用:图(graph)中的环检测

使用并查集(disjoint set)检测图(graph)是否存在环(cycle)

上图中第一个是一个图(graph),每个结点称为顶点(vertices),结点间的连线称为边(edge),现在的问题是在该图中检测环(闭环)。上图中将图中的结点简单地进行0~5标记,两个顶点组成一条边进行检测。如果有两个顶点(一条边)在同一个集合中,则存在一个环;如果两个顶点(一条边)不在一个集合中,则调用合并操作。

这里的关系R为顶点的连接,因此连接的两个顶点组成一个关系。这里仅仅简单结合图说一下不相交集的应用,下面会有相关的实现。

三、不相交集的实现方式和数据结构

不相交集的实现方式有两种,一种是链表,如下图是一个以1为代表的集合:

使用链表表示不相交集

使用链表时,链表中的每个元素表示一个集合成员,包含head和tail指针,head指针指向集合的一个元素(该元素称为一个集合的代表元素),一个指向下一个元素的指针,一个指向集合对象自身的指针,这里重点是谈下面的树的实现方式。

另一种方式是使用多路有根树,也叫并查集森林,这时候选取根元素作为集合的代表,每个结点保存父结点,根结点的父元素为自身,表示自身可以使用-1或0,如下图是一个以1为代表的集合:

使用有根树表示集合

由上面我们可以看到,对于集合中的数据元素我们是不需要显式表示的,只需要给结点元素做记号即可,也就是使用散列的方式描述元素,使用一个连续的数字序列即可。对于父结点,同样可使用数字序列,根结点的父结点为-1或0。

四、算法操作

这里是使用有根树的实现方式实现不相交集,对于优化的地方就不再一步步循序渐进地讲解,因为是树的原因,在合并的时候可以按照大小合并和按秩合并(按树高度),按大小合并也就是按照树的结点数量,总是将更小的树连接到更大的树上,按秩合并是将浅的树连接成为深的树的子树,这两种方式都是为了降低树的高度,这里实现使用的是按秩合并。

另外在合并操作的进一步优化则是路径压缩,它的意思是,尽量将结点的父结点指向根结点,这样查找起来更快速,下图是一个集合,以及该集合使用数组表示的形式,这里有两个数组parent和rank(单元素时集合的大小),中间current是数组的索引:

不相交集树和数组表示实例

以上是使用一个数组表示一个树,使用数组的索引为集合元素的记号,数组元素值为父结点的记号,下面是不相交集ADT的头文件声明代码:

// 不相交集ADT对外接口
typedef struct disjset{
    int *parent;
    int *rank;
    int n;
} DisjSet;

// 不相交集函数声明
extern DisjSet *disjset_new(int n);
extern void disjset_make_set(DisjSet *disjset, int n);
extern int disjset_find(DisjSet *disjset, int x); // root
extern int disjset_union(DisjSet *disjset, int x, int y); // 0: cycle, 1: union
extern int disjset_clear(DisjSet *disjset);
extern void disjset_cycle_detect(int array[][2], int n, int size);

1、创建集合make-set

首先我们需要创建n个单元素集合,每个元素的父元素为自身,代码如下:

DisjSet *disjset_new(int n){
    if(n < 1){
        perror("n is too small");
        return NULL;
    }
    DisjSet *disjset = (DisjSet*)malloc(sizeof(DisjSet));
    if(!disjset){
        perror("alloc memory for disjset error");
        return NULL;
    }
    disjset->n = n;
    disjset->parent = (int*)malloc(n * sizeof(int));
    if(!disjset->parent){
        perror("alloc memory for parent error");
        free(disjset);
        return NULL;
    }
    disjset_make_set(disjset, n);
    disjset->rank = (int*)malloc(n * sizeof(int));
    if(!disjset->rank){
        perror("alloc memory for rank error");
        free(disjset->parent);
        free(disjset);
        return NULL;
    }
    for (int j = 0; j < n; ++j)
        disjset->rank[j] = 0;
    return disjset;
}

void disjset_make_set(DisjSet *disjset, int n){
    if(disjset == NULL){
        perror("disjset null");
        return;
    }
    for (int i = 0; i < n; ++i)
        disjset->parent[i] = i;
}

2、查找find

该函数可以检查一个元素是否属于一个集合,也可以确定一条边(两个点)是否属于同一集合,返回之后为集合的代表(根),也就是一个集合,即等价类,路径压缩在这里实现,代码如下:

int disjset_find(DisjSet *disjset, int x){
    if(disjset == NULL){
        perror("disjset null");
        return 0;
    }
    // 压缩路径
    if(disjset->parent[x] != x)
        disjset->parent[x] = disjset_find(disjset, disjset->parent[x]);
    return disjset->parent[x];
}

3、联合union

该联合操作先调用find查找检查x、y是否在同一个等价类中,不在同一个等价类则执行合并操作,联合或合并两个集合成一个集合,该操作可以检查一个图是否存在环,合并优化采用按秩合并,这这里实现,代码如下:

int disjset_union(DisjSet *disjset, int x, int y){
    if(disjset == NULL){
        perror("disjset null");
        return 0;
    }
    int x_root = disjset_find(disjset, x);
    int y_root = disjset_find(disjset, y);
    if(x_root == y_root)
        return 0;
    // 按秩合并
    if(disjset->rank[x_root] > disjset->rank[y_root])
        disjset->parent[y_root] = x_root;
    else if(disjset->rank[x_root] < disjset->rank[y_root])
        disjset->parent[x_root] = y_root;
    else{
        disjset->parent[x_root] = y_root;
        disjset->rank[y_root] = disjset->rank[x_root] + 1;
    }
    return 1;
}

不相交集实现的算法相对比较简单,主要是不要忘记了优化的操作,如果没有进行按秩合并和路径压缩,那么树的高度可能会过高,当n越大,那么查找的速度也慢,以上项目完整源码可查看:https://github.com/onnple/disjset

五、不相交集的应用

1、图(graph)的环检测(cycle detection)

这是不相交集的主要应用,find查找操作确定特定元素在哪个子集中,这可以用来确定两个元素是否在同一个子集中,union联合操作将两个子集连接成一个子集,联合-查找算法可用于检查无向图是否包含环。

2、Kruskal最小生成树算法

在该算法中,同样是使用了不相交集的环检测算法。

3、工作序列最大利润问题

给定一组n个工作任务,其中每个工作任务i都有一个截止日期di >=1和利润>=0。一次只能安排一项工作。每项工作需要一个单位的时间来完成,当且仅当工作在最后期限前完成时,我们才能获利,任务目的是找到利润最大化的工作的子集,该问题可以借助不相交集进行解决。

赞(0) 打赏
未经允许不得转载:srcmini » 不相交集(disjoint set)原理和实现图文详解
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏