并查集(C++实现)

并查集这个很有意思，并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。昨天看书看到了，然后用C++简单实现了下。在Dijkstra算法中，用来判断两个顶点是否在同一个集合里。

里面定义了两个类，都是并查集，一个是QuickFind，查找很快，一个是QuickUnion，合并较快。写了一些注释，有一些优化的提示.看代码吧，有什么问题指出来吧。

QuickFind的实现

#include "QuickFind.h"

QuickFind::QuickFind(int N)
{
	size=N;
	id=new int[N];
	for(int i=0;i<N;i++)
	{
		id[i]=i;
	}
}

bool QuickFind::Find(int p,int q)
{
	return id[p]==id[q];
}

void QuickFind::Unite(int p,int q)
{
	int pid=id[p];
	for(int i=0;i<size;i++)
		if(id[i]==pid)
			id[i]=id[q];

}
QuickFind::~QuickFind(void)
{
	delete []id;
}

QuickUnion的实现

#include "QuickUnion.h"

QuickUnion::QuickUnion(int N)
{
	size=N;
	id=new int[N];
	for(int i=0;i<N;i++)
	{
		id[i]=i;
	}
}
int QuickUnion::root(int i)
{
	while (i!=id[i])
	{
		//id[i]=id[id[i]]; 若添加这句话则为压缩路径
		i=id[i];
	}
	return i;
}
bool QuickUnion::Find(int p,int q)
{
	return root(p)==root(q);
}

void QuickUnion::Unite(int p,int q)
{
	//将p的根挂在q的根上，
	//这样会导此数变高，若需要优化，需要设置另一个
	//数组sz[]，sz[i]表示所以根为i的节点的数目，然后将
	//小树靠在大树上

	/*
	int i=root(p);
	int j=root(q);
	if(sz[i]<sz[j])
	{
		id[i]=j;sz[j]+=sz[i];
	}
	else
	{
		id[j]=i;sz[i]+=sz[j];
	}*/
	int rootp=root(p);
	int rootq=root(q);
	id[rootp]=rootq;
}
QuickUnion::~QuickUnion(void)
{
	delete []id;
}

参考文档(英文)：UnionFind.pdf

工程代码下载：并查集Demo