不相交集合ADT

不相交集合数据结构保持一组不相交的动态集合S={S₁，S₂，...,S_K},每个集合通过一个代表来识别，代表即集合中的某个成员。

如果x表示一个对象，不相交集合支持以下操作：

MAKE-SET(x):建立一个新的集合，其唯一成员为x。因为各集合是不想交的，故x没有在其它集合中出现。

UNION(x,y):将包含x和包含y的集合合并为一个新的集合。

FIND-SET(x):返回包含x的集合。

1.不相交集合的数组表示

在一个数组中保存每个元素所在集合的名称。这样Find操作就是简单的O(1)查找。要执行Union(x,y)操作，假设x在等价类i中，y在等价类j中，

扫描整个数组，将所有的i变为j。连续N-1次Union操作就要花费Θ(N²)的时间。如果Union操作很多，这个界是不可接受的。

2.不相交集合的链表表示

每一个集合用用一个链表来表示。链表的第一个对象作为它所在集合的代表。链表中每个对象都包含一个集合成员，一个指向下一个对象的指针，

以及指向代表的指针。每个链表含head和tail指针，head指向链表的代表，tail指向链表中最后的对象。

Union的简单实现：将x所在的链表拼接到y所在链表的表尾。对于原先x所在链表中的每一个对象都要更新其指向代表的指针。

平均看来，每个操作需要Θ(N)的时间。

加权合并：每个表含表的长度，总是将更短的表连接到长的表的后面。这样，m和MAKE-SET,UNION和FIND-SET操作要花费(m+nlgn)的时间。

class SetNode(object):

    def __init__(self,key):

        self.key=key

        self.next=None

        self.rep=None

class SetEntry(object):

    def __init__(self):

        self.head=None

        self.tail=None

        self.len=0

class DisjSet(object):

    def __init__(self,node):

        self.setlist=[]

    def make_set(self,node):

        S=SetEntry()

        S.head=node

        S.tail=node

        S.len=1

        node.rep=node

        self.setlist.append(S)

    def find(self,node):

        return node.rep

    def union(self,node_x,node_y):

        rep_x=node_x.rep

        rep_y=node_y.rep

        if rep_x!=rep_y:

            for s in self.setlist:

                if s.head==rep_x:

                    set_x=s

                elif s.head==rep_y:

                    set_y=s

            if set_x.len>=set_y.len:

                set_x.tail.next=rep_y

                node=rep_y

                while node is not None:

                    node.rep=rep_x

                    node=node.next

                set_x.tail=set_y.tail

                set_x.len=set_x.len+set_y.len

                self.setlist.remove(set_y)

                return rep_x

            else:

                set_y.tail.next=rep_x

                node=rep_x

                while node is not None:

                    node.rep=rep_y

                    node=node.next

                set_y.tail=set_x.tail

                set_y.len+=set_x.len

                self.setlist.remove(set_x)

                return rep_y

　3.不相交集合森林

使用树来表示一个集合，树的根用来作为集合的代表。树的每个节点都含有元素的数据以及一个指向父节点的指针。根节点的指针为空。

可以用数组来非显式的来表示树：数组的每个成员T[i]表示元素i的父节点，如果i是根，取p[i]为0或者-1。

如果任意执行Union操作，树可能会变为退化树，有几种方法可以避免这种情况

3.1 灵巧求并算法

总是让更小的树成为较大的树的子树，称为按大小求并。另一种方法是按高度求并。

这样的话，任何节点的深度都不会超过logN，Find操作的运行时间是O(logN),而连续M次操作则花费O(MlogN)。

实现时，让数组每个元素包含它的树的大小的负值。

class DisjSet(object):

    def __init__(self,size):

        self.list=[-1]*size

    def find(self,x):

        if self.list[x]<0:

            return x

        else:

            return self.find(self.list[x])

    def union(self,x,y):

        set_x=self.find(x)

        set_y=self.find(y)

        if set_x!=set_y:

            if self.list[set_x]>self.list[set_y]:

                self.list[set_y]+=self.list[set_x]

                self.list[set_x]=set_y

                return set_y

            else:

                self.list[set_x]+=self.list[set_y]

                self.list[set_y]=set_x

                return set_x

3.2 路径压缩

路径压缩在一次Find(X)操作期间执行，从X到根的路径上的每一个节点都使它的父节点变成根。

路径压缩与按大小求并是完全兼容的，而不完全与按高度求并兼容。路径压缩时每棵树的高度会发生变化，可以对每棵树所存储的高度估计，用秩rank表示。

class DisjSet_with_rank(object):

    def __init__(self,size):

        self.list=[-1]*size

    def find(self,x):

        if self.list[x]<0:

            return x

        else:

            self.list[x]=self.find(self.list[x])

            return self.list[x]

    def union(self,x,y):

        set_x=self.find(x)

        set_y=self.find(y)

        if set_x!=set_y:

            if self.list[set_x]<self.list[set_y]:

                self.list[set_y]=set_x

            else:

                if self.list[set_x]==self.list[set_y]:

                    self.list[set_y]-=1

                self.list[set_x]=set_y

路径压缩的显式表示　　

class SetNode(object):

    def __init__(self,key):

        self.parent=None

        self.key=key

        self.rank=1

def find(node):

    if node.parent is None:

        return node

    else:

        node.parent=find(node.parent)

        return node.parent

def union(x,y):

    x=find(x)

    y=find(y)

    if x!=y:

        if x.rank<=y.rank:

            if x.rank==y.rank:

                y.rank+=1

            x.parent=y

            return y

        else:

            y.parent=x

            return x

巴特西

不相交集合ADT

1.不相交集合的数组表示

2.不相交集合的链表表示

3.不相交集合森林

最新文章

热门文章