注册 登录
编程论坛 数据结构与算法

并查集合问题

mhchen2010 发布于 2013-07-03 15:09, 597 次点击
typedef struct node
{  int data;        //结点对应人的编号
   int rank;        //结点对应秩
   int parent;        //结点对应双亲下标
} UFSTree;            //并查集树的结点类型

void MAKE_SET(UFSTree t[]) //初始化并查集树
{  int i;
   for (i=1;i<=N;i++)
   {  t[i].data=i;    //数据为该人的编号
     t[i].rank=0;    //秩初始化为0
     t[i].parent=i;    //双亲初始化指向自已
   }
}




int FIND_SET(UFSTree t[],int x)   
//在x所在子树中查找集合编号
{  if (x!=t[x].parent)    //双亲不是自已
    return(FIND_SET(t,t[x].parent));
                   //递归在双亲中找x
   else
    return(x);        //双亲是自已,返回x
}








void UNION(UFSTree t[],int x,int y)
//将x和y所在的子树合并
{  x=FIND_SET(t,x);    //查找x所在分离集合树的编号
   y=FIND_SET(t,y);    //查找y所在分离集合树的编号
   if (t[x].rank>t[y].rank)//y结点的秩小于x结点的秩
    t[y].parent=x;     //将y连到x结点上,x作为y的孩子结点
   else            //y结点的秩大于等于x结点的秩
   {  t[x].parent=y;    //将x连到y结点上,y作为x的孩子结点
    if (t[x].rank==t[y].rank)    //x和y结点的秩相同
       t[y].rank++;    //y结点的秩增1
   }
}


1)t[x]的秩大于t[y]的秩,应该是y接到x上,怎么是x接到Y上呢

2)t[y].parent=x;     //将y连到x结点上,x作为y的孩子结点
我感觉这句话中的程序和解释说反了?
2 回复
#2
holy__shit2013-08-23 02:19
回复 楼主 mhchen2010
1.t[x] > t[y]则x > y   用小下标y
2.t[x] <= t[y]则 x <= y 用小下标x
#3
赵富强2016-11-06 13:59
1