[树](6)树的等价关系

在离散数学中,等价类的定义是:
如果集合S中的关系R是自反的对称的传递的,则称它是一个等价关系。

集合S上的关系R可定义为,集合SXS的笛卡尔积的子集,即关系是序对的集合。

若R是集合S上的等价关系,则由这个等价关系可产生这个集合的惟一划分,即可以按R将S划分为若干不相交的子集S1,S2....S3,S4.......,它们即为S,则这些子集Si便称为S的R等价类

等价关系是现实世界中广泛存在的一种关系,许多应用问题可以归结为按给定的等价关系划分某集合的等价类

  • 等价关系,其实是物体局部性质的等同,在限定条件下可替换性,例如:
  • 初中几何的三角形相似,相似是一种等价关系,它忽略了三角形的大小,但是确定了三角形的形状,相似其实是三角形角度的相等,所以在计算cos,sin等性质的时候都是相等的。

img大佬的白话理解

例如在ForTran语言中,可以利用EquivaLence语句使数个程序变量共享同一存储单位,这问题实质就是按EquivaLance语句确定的关系对程序中的变量集合进行划分

所得等价类的数目即为需要分配的存储单位,而同一等价类中的程序变量可被分配到同一存储单位去,此外,划分等价类的算法思想也可用于求网络的最小生成树等图的算法中

假设集合S有n个元素,m个形如( x , y ) ( x , y ∈ S )的等价偶对确定了等价关系R,现在求S的划分:

  • 令S中的每个元素各自形成一个只含单个成员的子集,记作S1 , S2 , . . . , Sn
  • 重复读入m个偶对,对每个读入的偶对( x , y ),判定x和y所属的子集。不失一般性,假设x ∈ Si , y ∈ Sj若Si ≠ Sj则将Si并入Sj并置S i S_{i}Si为空(或反过来)。
  • 则当m个偶对都被处理过后,S 1 , S 2 , . . . , S n中所有非空子集即为S的R等价类。

从上述可见,划分等价类需对集合进行的操作有三个:

  • 构造只含单个成员的集合
  • 判定某个单元素所在的子集
  • 归并两个互不相交的集合为一个集合

由此,需要一个包含上述3中操作的抽象数据类型MFSet

ADT MFSet{
          数据对象:若设S是MFset型的集合,则它由n(n>0)个子集                              Si(i=1,2,3,4,......,n)构成,
          每个子集的成员都是子界[- maxnumber..maxnumber]

          数据关系:S1 U S2 U S3 .... U Sn = S     Si ⊂ S(i = 1,2,3....n)

          基本操作:
          Initial(&S,n,X1,X2,.....,Xn);
               操作结果:初始化操作。构造一个由n个子集
              (每个子集只包含单个成员Xi)构成的集合S.
          Find(S,x)
               初始条件:S是已存在的集合,x是S中某个子集的成员
               操作结果:查找函数。确定S中x所属子集Si。
          Merge(&S,i,j)
               初始条件:Si和Sj是S中两个互不相交的非空集合
               操作结果:归并操作。将Si和Sj中的一个并入另一个中
}ADT MFSet

以集合为结构的抽象数据类型可用多种方法实现方法,如用位向量表示集合或用有序表表示集合等

如何高效的实现以集合为基础的是抽象数据类型,则取决于该集合的大小以及对此集合所进行的操作

根据MFSet类型中定义的查找函数和归并操作的特点,我们可利用树型结构表示集合,约定:

  • 以森林F=(T1,T2...Tn)表示MFSet型的集合S
  • 森林中的每一颗树Ti(i=1,2,...n)表示S中的一个元素

    • 子集Si(Si属于S,i=1,2,...,n)树中每个结点表示子集中的成员x

为操作方便起见,令每个结点中含有一个指向其双亲的指针,并约定根结点的成员兼作子集的名称

例下图中的两棵树分别表示子集S1={1,3,6,9}和S2={2,8,10}

img

显然,这样的树型结构易于实现上述两种集合的操作,由于各子集中的成员均不相同,则实现集合的“并”操作,只要将一棵子集树的根指向另一棵子集树的根即可

同时,完成找到某个成员所在集合的操作,只要从该成员结点出发,顺链而进,直至找到树的根结点位置

为便于实现这样两种操作,应采用双亲表示法作存储结构,如下所示:

int find_mfset(MFSet S, int i)
//找集合S中i所在子集的根
{
    if (i<1 || i>S.n) return -1;
    for (int j = i, S.nodes[j].parent > 0; j = S.nodes[j].parent);
    return j;
}

Status merge_mfset(MFSet* S, int i, int j)
//S.nodes[i]和S.nodes[j]分别为S的互不相交的两个子集Si和Sj的根结点
//求并集Si U Sj
{
    if (i<1 || i>S.n || j<1 || j>S.n) return ERROR;
    S.nodes[i].parent = j;
    return OK;
}

上述查找函数的时间复杂度为O(d)和O(1),其中d是树的深度,从前面的讨论可知,这种表示集合的树的深度和树形成的过程有关。

试看一个极端的例子,假设有n个子集 S1,S2,......,Sn,每个子集只有一个成员Si={i}(i=1,2,...,n),可用n棵只有一个根结点的树,现作n-1次“并”操作,并假设每次都是含成员多的根结点指向含成员少的根结点

则最后得到的集合树的深度为n,如果再加上每次“并”操作之后都要进行查找成员“1”所在的子集的操作,则全部操作的时间便是O(n²)了,如下图所示:

img

改进的办法是在作”并“操作之前先判别子集中所含元素的数目,然后令成员少的子集树根指向含成员多的子集树根,为此,需相应的修改存储结构,然后令根结点的parent域存储子集中所含成员数目的负值

修改后的归并算法如下所示:

void mix_mfset(MFSet* S, int i, int j)
//S.nodes[i]和S.nodes[j]分别为S的互不相交
//的两个子集Si和Sj的根结点,求并集Si U Sj
{
    if (i<1 || i>S.n || j<1 || j>S.n) return ERROR;

    if (S.nodes[i].parent > S.nodes[j].parent)
        //Si所含成员数比Sj少
    {
        S.nodes[j].parent += S.nodes[i].parent;
        S.nodes[i].parent = j;
    }
    else
    {
        S.nodes[i].parent += S.nodes[j].parent;
        S.nodes[j].parent = i;
    }
    return OK;
}

可以证明,按上述算法进行”并“操作得到的集合数,其深度不会操作log2n+1,其中n为集合S中所有子集所含成员数的总和

由此,利用算法find_mfset和mix_mfset解等价问题的时间复杂度为O(nlogn)(当集合中有n个元素时,至多进行n-1次mix操作)

我们来看一个例子:假设集合S={x|1<=x<=n(n是正整数)} R是S上的一个等价关系

R={(1,2),(3,4),(5,6),(7,8),(1,3,),(5,7),(1,5),...}

现求S的等价类

以MFSet类型的变量S表示集合S,S中成员个数为S.n,开始时,由于每个成员自成一个等价类,则S.nodes[i].parent的值均为-1,之后,每处理一个等价偶对(i,j)首先必须确定i和j各自所属集合

若这两个集合相同,则说明此等价关系是多余的,无需作处理,否则就合并着两个集合,下图展示处理R中前7个等价关系时S的变化状况(注意图中省去了结点的数据域)。

img

下图所示和最后一个S状态相应的树的形态。

img

显然,随着子集逐对合并,树的深度也越来越大,为了进一步减少确定元素所在集合的时候,我们还可进一步讲算法改进,当所查元素i不在树的第二层时,在算法中增加一个"压缩路径"的功能,即将所有从根到元素i路径上的元素都变成树根的孩子

int fix_mfset(MFSet* S, int i)
//确定i所在子集,并将从i至根路径上所有结点上所有结点都变成根的孩子
{
    if (i<1 || i>S.n) return -1;//i不是S中任一子集的成员
    int j;
    for (j = i; S.nodes[j].parent > 0; j = S.nodes[j].parent);
    for (int k = i; k != j; k = t)
    {
        t = S.nodes[k].parent;
        S.nodes[k].parent = j;
    }
    return j;
}

假设上述例子中第八个等价偶对为(8,9),则在执行fix(s,8)的操作之后,上图中左边的状态就变为了右边的状态

以及证明,利用算法fix_mfset和mix_mfset划分大小为n的集合为等价类的时间复杂度为O(na(n)),其中a(n)是一个增长极其缓慢的函数,若定义单变量的阿克曼函数为A(x)=A(x,x),则函数a(n)定义为A(x)的拟逆,即a(n)的值是使A(x)>=n成立最小的x,所以,对于通常所见的正整数n而言,a(n)<=4

本文链接:

https://nullcode.fun/123.html
1 + 2 =
快来做第一个评论的人吧~