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 {
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 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 {
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;
}