标题:并查集合问题
取消只看楼主
mhchen2010
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2012-12-25
结帖率:0
 问题点数:0 回复次数:0 
并查集合问题
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的孩子结点
我感觉这句话中的程序和解释说反了?
搜索更多相关主题的帖子: parent 
2013-07-03 15:09



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-416579-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.240313 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved