算法导论 第二十一章:不相交集合的数据结构

不相交集合(Disjoint-set )数据结构保持一组不相交的动态集合S={S(1),S(2),...,S(k)}.每个集合通过一个代表(representative)来识别,即集合中的某个成员。设x表示一个对象,不相交集合支持操作:

MAKE-SET(x):建立一个新的结合,其唯一成员(也即代表)就是x。因为各集合是不相交的,故要求x没有在其他集合中出现过。

UNION(x,y):将包含x和y的动态集合合并成一个新的集合(即这两个集合的并集)。假定在这个操作之前两个集合是不相交的,操作之后,选取集合S(x)或S(y)的代表作为新代表。

FIND-SET(x):返回一个指向包含x的(唯一)集合的代表

不相交集合数据结构的一个应用:

确定一个无向图连通子图的个数。过程如下:

下面过程CONNECTED-COMPONENTS利用不相交集合操作来计算一个图的连通子图:

一旦CONNECTED-COMPONETS作为预处理步骤执行后,SAME-COMPONENT判断两个顶点是否在同一连通子图中:

不相交集合的链表表示

如合并的操作中,一种简单的操作方式是采用链表集合表示来实现,如下图:

利用链表结构实现上述应用的完整代码如下:

#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#define N 256
using namespace std;

typedef struct setNode{
	char key;
	setNode *next;
	setNode *representative;
	setNode(char k):key(k),next(NULL),representative(NULL){}
	}setNode;

typedef struct Set{
	int num;
	setNode *head;
	setNode *tail;
	}Set;

typedef struct edge{
	char u;
	char v;
	}edge;

Set Make_Set(char k)
{
	setNode *x=new setNode(k);
	Set *s = new Set();
	s->head = x;
	s->tail = x;
	s->num  = 1;
	x->representative = x;
	return *s;
	}
setNode *Find_Set(Set s)
{
	return s.head->representative;
	}

void Update_Representative(setNode *head, setNode *representative)
{
	setNode *p=head;
	while(p != NULL)
	{
		p->representative = representative;
		p = p->next;
 		}
	}
void PrintSet(Set x)
{
	setNode *p = x.head;
	while(p != NULL)
	{
		cout<<p->key<<"   ";
		p = p->next;
 		}
	cout<<endl;
	}
void Print_conComponents(Set LinklistSet[],int n)
{
	int count=1;
	for(int i=0; i<n; i++)
		if(LinklistSet[i].num != 0){
			cout<<"Connect component "<<count<<" is:";
			PrintSet(LinklistSet[i]);
			count++;
			}
	   	}
void Set_Union(Set &x,Set &y)
{
	 if (x.num < y.num){
		Set temp;
		temp = x;
		   x = y;
		   y = temp;
		}
	Update_Representative(y.head, x.head);
	x.tail->next = y.head;
	x.tail = y.tail;
	x.num += y.num;
	y.num  =0;
	}
void LinklistSet_Create(Set LinklistSet[],char vertex[],int vNum)
{
	for(int i=0;i<vNum;i++)
	{
	    int index=(int)vertex[i];                  //eg.a->97,b->98,...
		LinklistSet[index] = Make_Set(vertex[i]);
	 	}
	}

void Compute_conComponents(Set LinklistSet[],edge edgeArray[],int eNum)
{//Compute the component forest
	for(int i=0;i<eNum;i++)
	{
		Set *set_u = &LinklistSet[(int)edgeArray[i].u];   //use the pointer to change the LinklistSet[] info
		Set *set_v = &LinklistSet[(int)edgeArray[i].v];

		if (Find_Set(*set_u) != Find_Set(*set_v)){
			//Set_Union(LinklistSet[(int)edgeArray[i].u],LinklistSet[(int)edgeArray[i].v]);
			Set_Union(*set_u,*set_v);
			}

		}
	}
int main()
{
	char vertex[]={'a','b','c','d','e','f','g','h','i','j'};
	edge edgeArray[]={{'b','d'},{'e','g'},{'a','c'},{'h','i'},{'a','b'},{'e','f'},{'b','c'}};
	int vNum=sizeof(vertex)/sizeof(char);
	int eNum=sizeof(edgeArray)/sizeof(edge);
	Set LinklistSet[N]={NULL};

	LinklistSet_Create(LinklistSet,vertex,vNum);           //link list set create
	Compute_conComponents(LinklistSet,edgeArray,eNum);
	Print_conComponents(LinklistSet,N);

	return 0;
	}

运行结果:

【注:若有错误,请指点~~~~】

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 07-17

算法导论 第二十一章:不相交集合的数据结构的相关文章

算法导论 第二十一章:不相交集合森林

在不相交集合中的另一种更快的实现中,用有根树来表示集合.树中的每个成员指向其父节点,每棵树的根包含了代表(representative),并且是他自己的父节点.不相交森林即由多棵这样的树组成,如下图所示: [注:(b)是(a)UNION(e,g)的结果] 采用上述表示方法直观上并不比采用链表表示算法更快,但是可以通过"按秩合并"和"路径压缩"来提升效率. 按秩合并(union by rank): 对于每个节点,用秩表示节点高度的一个上界.在按秩合并中,具有较小秩的跟

算法导论第十一章 散列表

一.散列表的概念 本章介绍了散列表(or hash table)的概念.散列函数的设计及哈希冲突的处理.散列表(为了形象描述,我们通常叫槽)从表意上看是一种数据结构,但把它归为算法思想更为贴切.对于大部分的查找问题,使用散列表能达到O(1)的效率.现在很多大公司在面试大数据的题目时,解决方案里绝对少不了散列表的思想,例如百度的一道面试题:Top K查找问题: 问题描述: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节. 假设目前有一千万个记录(这

算法导论 第二章

2014-12-02 20:21:40 http://www.cnblogs.com/sungoshawk/p/3617652.html 上面链接指向算法导论第二章的预习博客,很值得一看,很详细. 插入算法: 1 #include <iostream> 2 3 using namespace std; 4 void insert_sort(int *datas, int length); 5 int main() 6 { 7 int a[10]={1,2,4,35,6,1,4,7,9,7};

算法导论 第13章 红黑树

二叉查找树的基本操作包括搜索.插入.删除.取最大和最小值等都能够在O(h)时间复杂度内实现,因此能在期望时间O(lgn)下实现,但是二叉查找树的平衡性在这些操作中并没有得到维护,因此其高度可能会变得很高,当其高度较高时,而二叉查找树的性能就未必比链表好了,所以二叉查找树的集合操作是期望时间O(lgn),最坏情况下为O(n). 红黑树也是一种二叉查找树,它拥有二叉查找树的性质,同时红黑树还有其它一些特殊性质,这使得红黑树的动态集合基本操作在最坏情况下也为O(lgn),红黑树通过给节点增加颜色和其它

算法导论 第6章 堆排序

堆数据结构实际上是一种数组对象,是以数组的形式存储的,但是它可以被视为一颗完全二叉树,因此又叫二叉堆.堆分为以下两种类型: 大顶堆:父结点的值不小于其子结点的值,堆顶元素最大 小顶堆:父结点的值不大于其子结点的值,堆顶元素最小 堆排序的时间复杂度跟合并排序一样,都是O(nlgn),但是合并排序不是原地排序(原地排序:在排序过程中,只有常数个元素是保存在数组以外的空间),合并排序的所有元素都被拷贝到另外的数组空间中去,而堆排序是一个原地排序算法. 1.在堆排序中,我们通常使用大顶堆来实现,由于堆在

算法导论 第6章 堆排序(简单选择排序、堆排序)

堆数据结构实际上是一种数组对象,是以数组的形式存储的,可是它能够被视为一颗全然二叉树,因此又叫二叉堆.堆分为下面两种类型: 大顶堆:父结点的值不小于其子结点的值,堆顶元素最大 小顶堆:父结点的值不大于其子结点的值,堆顶元素最小 堆排序的时间复杂度跟合并排序一样,都是O(nlgn),可是合并排序不是原地排序(原地排序:在排序过程中,仅仅有常数个元素是保存在数组以外的空间),合并排序的全部元素都被复制到另外的数组空间中去,而堆排序是一个原地排序算法. 1.在堆排序中,我们通常使用大顶堆来实现,因为堆

算法导论 第2章

本章主要是算法知识的基础讲解,介绍了循环不变式,几个简单的排序算法,递归分治算法等内容. 1.循环不变式 循环不变式主要用来说明算法的正确性,那么什么是循环不变式呢,其实就是在循环过程中,一些元素数据必须保持的一些性质,例如在插入排序中,数组为A,必须保证三个性质: (1) 初始化:在循环开始之前,循环不变式是成立的,即:A[0]是有序的,A[1...n-1]是无序的. (2) 保持:在循环的某一次迭代开始之前,循环不变式是成立的,那么在此次迭代结束后依然应该是成立的,即:A[0...i]是有序

从零开始的linux 第二十一章(Inode以及Block详解其二与软链接)

从零开始的linux 第二十一章 在紧张的学习中,又迎来了新的一周~~小编也在同学们的迫切要求下继续来更新博客咯~~ 同学们:"我们才没要求你!" 唉??同学们一点都不配合呢~~别不好意思嘛~~ 好啦~不逗你们了,小编就节省大家的时间,赶快开始这章的课程吧~~ 在上一章中,小编给同学们讲了 Inode号 和 Block,不过还没有给同学们讲完哦~所以上一章的题目是 其一 ,那么毫无疑问这一章就是其二的内容咯~从上一章同学们已经了解了什么是Inode和Block,以及Inode中包含哪些

2017.2.15 开涛shiro教程-第二十一章-授予身份与切换身份(一) table、entity、service、dao

原博客地址:http://jinnianshilongnian.iteye.com/blog/2018398 根据下载的pdf学习. 第二十一章 授予身份与切换身份(一) 1.使用场景 某个领导因为某些原因不能访问一些网站,他想把这个网站上的工作委托给秘书,但是他又不想提供账户.密码.此时可以使用shiro的 RunAs 功能. RunAs:允许一个用户假装为另一个用户(如果获得了允许)的身份进行访问. 注意,本章代码基于<第十六章 综合实例>,详细的数据模型及基本流程见该章. 2.表及数据