不相交集合

在某些应用中,要将n个不同的元素分成一组不相交的集合,不相交集合上有两个重要的操作,即找出给定的元素所属的集合和合并两个集合(如Kruskal最小生成树算法)。

性质:哪一个成员被选为作为集合的代表无关紧要,如果在一个集合未被修改的情况下,两次寻找此集合代表得到的结果应该是相同的。

操作:1,MAKE-SET(x),建立一个新的集合,其唯一成员就是x,要求x未在其他集合中出现过(以为各个集合要求不相交)。

            2,UNION(x,y),将包含有x和y的动态集合合并成一个新的集合。

            3,FIND-SET(x),返回指向包含对象x的的集合的代表指针。

表示:

1,链表表示:

      一个链表表示一个动态集合,链表的结点中包含对象、一个next指针和一个指向所在链表代表的指针(链表的头指针),每个链表都有一对head和tail指针,链表中对象无序,链表的头结点作为它所表示的集合的代表。

     MAKE-SET(x)创建一个链表,x为唯一结点。

     FIND-SET(x)返回x所在链表的头结点。

     UNION(x,y)将x所在链表接在y所在链表的末尾,因为有head和tail指针,所以操作起来比较快,两个链表连接之后需要更新x所在链表的每个节点指向集合代表的指针(即从合并前的x所在链表的头结点指向y所在链表的头结点)。

2,有根树表示:


应用:

1,计算一个无向图中连通子图的个数(不相交集合表示各个子图,子图的顶点表示各不相交集合的对象)

相关文章
相关标签/搜索