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

在不相交集合中的另一种更快的实现中,用有根树来表示集合。树中的每个成员指向其父节点,每棵树的根包含了代表(representative),并且是他自己的父节点。不相交森林即由多棵这样的树组成,如下图所示:

[注:(b)是(a)UNION(e,g)的结果]

采用上述表示方法直观上并不比采用链表表示算法更快,但是可以通过“按秩合并”和“路径压缩”来提升效率。

按秩合并(union by rank):

对于每个节点,,用秩表示节点高度的一个上界。在按秩合并中,具有较小秩的跟在UNION操作中要指向具有较大秩的根。

路径压缩(path compression):

在FIND-SET操作中,利用这种启发式策略来使查找路径上的每个节点都直接指向根节点。(路径压缩不改变节点的秩)

相关操作伪代码如下:

需要说明的是,上述FIND-SET过程采用一种两趟方法(two-pass method):一趟是沿查找路径上升,直到根;第二趟是沿查找路径下降,以便更新每个节点,使之直接指向根。

不相交森林实现连通子图的完整代码如下:

#include<iostream>#include<string>#include<cstdlib>#include<vector>using namespace std;typedef struct setNode{char key;int rank;setNode *parent;setNode(char k):key(k),rank(0),parent(NULL){}}setNode;typedef struct Set{setNode *root;}Set;typedef struct edge{char u;char v;}edge;setNode *Make_Set(char k){setNode *x=new setNode(k);x->parent = x;return x;}setNode *Find_Set(setNode *x){if(x != x->parent)x->parent=Find_Set(x->parent);return x->parent;}void Link(setNode *x,setNode *y){if(x->rank > y->rank)y->parent = x;else{ x->parent = y;if(x->rank == y->rank)y->rank = y->rank + 1;}}void Set_Union(setNode *x,setNode *y){Link(Find_Set(x),Find_Set(y));setNode *z=Find_Set(x);}void forestSet_Create(Set forestSet[],char vertex[],int vNum){for(int i=0;i<vNum;i++){int index=(int)vertex[i];//eg.a->97,b->98,…forestSet[index].root = Make_Set(vertex[i]);}}void Compute_conComponents(Set forestSet[],edge edgeArray[],int eNum){//Compute the component forestfor(int i=0;i<eNum;i++){setNode *set_u=forestSet[(int)edgeArray[i].u].root;setNode *set_v=forestSet[(int)edgeArray[i].v].root;if (Find_Set(set_u) != Find_Set(set_v))Set_Union(set_u,set_v);} }void Print_conComponents(Set forestSet[],char vertex[],int vNum){//classify the forest and print the connect components and the representativestring representative;for(int i=0;i<vNum;i++){setNode *t;t=Find_Set(forestSet[(int)vertex[i]].root);if(representative.find(t->key) == -1)//the char t is not in representativerepresentative += t->key;}cout<<"The representative of the forest:"<<representative<<endl;int repLen=representative.length();vector<char> *ComponentsVec = new vector<char>[repLen]; for(int i=0; i<vNum; i++) {setNode *temp;temp=Find_Set(forestSet[(int)vertex[i]].root);int index=representative.find(temp->key);ComponentsVec[index].push_back(vertex[i]);}for(int i=0; i<repLen; i++){cout<<"The connect component "<<i+1<<" is:";for(int j=0; j<ComponentsVec[i].size(); j++)cout<<ComponentsVec[i].at(j)<<" ";cout<<endl;} }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 forestSet[256]={NULL};forestSet_Create(forestSet,vertex,vNum);//Create forest setCompute_conComponents(forestSet,edgeArray,eNum); //Computing the component forestPrint_conComponents(forestSet,vertex,vNum);return 0;}运行结果:

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

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

鸟儿爱美,不仅需要羽毛之美,还需要鸣声婉转之美;

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

相关文章:

你感兴趣的文章:

标签云: