并查集(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]&lt;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

comments powered by Disqus