数据结构重读 – 树和等价问题(并查集)

数据结构这书感觉和之前没读过一样……以前从来没发现树这章还讲了并查集……

若R是集合S上的一个等价关系,则由这个等价关系可以产生这个集合的唯一划分。

如何划分等价类

假设集合S有n个元素,m个形如(x, y),的等价偶对(x, y都是集合S中的元素)。

(1)令S中每个元素各自形成一个只含单个成员的子集,记作S1, S2, …, Sn。
(2)依次读入m个偶对,对每个读入的偶对(x, y),判定x和y所属的集合,若他们还不属于同一集合,设x属于Si,y属于Sj,则合并Si和Sj。

集合操作的实现与并查集

其实上面描述的这种集合操作,归结起来有两个重要的:

Init(S):令集合S中的每个元素x,单独称为一个集合Sx。

Find(x):确定x属于那个子集合Si。

Merge(i, j):合并子集合Si和Sj。

这些操作可以有很多实现方法,例如用位向量、有序表等。

此外,还可以使用并查集

(1)将集合中的每个元素用结点表示,每个结点中含有一个指向其双亲的指针。
(2)约定根结点的成员做为子集合的类名。
根据上述规定,实现集合”并”(Merge)操作,只需要让一棵树的根指向另一棵即可。
而实现查找,就是依次向parent查找,直到到达该树的根。

下述是这种基础版本的并查集,其Find和Merge的时间复杂度分别为O(d)和O(1),d是树的深度。

#include <stdio.h>

#define MAX 100
int parent[MAX];

void uf_init()
{
	int i;
	for(i=0;i<MAX;i++)
	{
		parent[i] = i;
	}
}

void uf_union(int i, int j)
{
	if(i<0 || i>=MAX || j<0 || j>=MAX)
	{
		return ;
	}
	int px = uf_find(i);
        int py = uf_find(j);
        parent[px] = py;
}

int uf_find(int x)
{
	if(x<0||x>=MAX)
	{
		return -1;
	}
	if(parent[x]==x)
	{
		return parent[x];
	}else
	{
		return uf_find(parent[x]);
	}
}

int main()
{
	int i;
	uf_init();
	uf_union(0, 1);
	for(i=0;i<10;i++)
	{
		printf("%d\n", uf_find(i));
	}
	return 0;
}

并查集优化

(1)rank,秩的压缩,即总是把含孩子少的合并到孩子多的子树上。以减少不平衡树的产生。但是话说这个优化感觉有限。

(2)路径压缩。实际是记忆搜索的变种。如下:

int uf_find(int x)
{
	if(x<0||x>=MAX)
	{
		return -1;
	}
	if(parent[x]==x)
	{
		return parent[x];
	}else
	{
		return uf_find(parent[x]);
	}
}

上述优化后,查找和合并的时间复杂度都可以认为是常数级别。

 

 

Leave a Reply

Your email address will not be published.