算法导论中的不相交集合的链表实现


不相交集合上的操作

算法导论中有提到不相交集合的两个重要操作,即找出给定的元素所属的集合和合并两个集合。我们首先要清楚,什么是不相交集合?顾名思义,就是集合上,没有相交的元素,交叉集为空集。这个时候,每个集合需要一个代表来识别,代表即集合中的某个成员,集合中的每个成员的代表都是相同的。然后判断某两个成员是否在同一个集合中,只需要判断代表是否相等就可以了。

    不相交集合必须支持以下操作:

        MAKE_SET(x):建立一个新的集合。其唯一的成员就是x。因为各集合是不相交的,故要求x没有在其他集合中出现过。

        FIND_SET(x):返回一个指针,指向包含x的唯一集合的代表

        UNION_SET(x,y) :将包含x和y的动态集合(比如Sx和Sy)合并为一个新的集合。  

    这种不相交集合有什么应用呢?其中之一是用于确定一个无向图中连通子图的个数。

不相交集合的链表表示

要实现不相交集合数据结构。一种简单的方法是每个集合都用一个链表来表示。每个链表中的第一个对象作为它所在集合的代表。链表中的每个对象都包含一个集合成员、一个指向包含下一个集合成员的对象的指针,以及指向代表的指针。而每个链表度包含head和tail指针,head指针指向链表的代表,tail指向链表中的最后一个对象。在每个链表中,对象可以以任意的顺序出现。

合并操作的简单实现

合并操作的话,有一个简单的实现,合并x,y时,直接将x集合的tail指针指向y集合的head指针,然后更新y集合中各对象的代表指针值。

       实际上,不难给出一个作用于n个对象上的、包含m个操作的序列,它需要O(n^2)时间。假设有对象x1,x2,...xn。在这些对象上,执行n个MAKE_SET操作,后跟n-1个UNION_SET操作,因而有m = 2n - 1。 执行n个MAKE_SET操作所需时间为O(n),因为第i个UNION操作更新了i对象,故n-1个UNION操作所更新的对象总数为 

    级数∑i=1到N-1 = O(N^2)

总的操作数为2n-1,因而,平均看来,每个操作需要O(n)的时间。

合并操作的加权合并启发式策略

我们从合并操作的简单实现中发现,合并x和y时,都会遍历y,不管y集合中的元素个数是否多于x。现在,我们假设每个链表中包含了表的长度,并且总是把较短的表拼接到较长的表上去;如果两个表一样长,则任意拼接。利用这种简单的加权合并启发式 策略,一个包含m个MAKE_SET、UNION、FIND_SET操作(其中有n个是MAKE_SET操作)的序列所需时间为O(m+nlgn)。

示例代码 

代码使用了模板技术。

#include <iostream>
#include <map>

using namespace std;

template <class T>
struct LinkNode
{
    T val;
    LinkNode *next;
    LinkNode * repr;
};

template <class T>
struct LinkList
{
    LinkNode<T> *head;
    LinkNode<T> * tail;

    T size;
};

template<class T>
class NonInterSect
{
public:
    NonInterSect(){}
    ~NonInterSect();

    void make_set(T val);

    LinkNode<T>* find_set(T val);

    void union_set(T u, T v);

    void prTset();

private:
    void update_repr(LinkNode<T>* head, LinkNode<T> * repr);
    void prTlist(LinkNode<T>* head);
private:
    map<T, LinkList<T> *> linkmap;
    map<T, LinkNode<T>* > nodemap;
};

template<class T>
NonInterSect<T>::~NonInterSect()
{
    //释放空间
    typename map<T, LinkList<T>* >::iterator lit;

    for(lit = linkmap.begin(); lit != linkmap.end(); ++lit)
    {
        LinkNode<T>* p = lit->second->head;

        while(p != NULL)
        {
            LinkNode<T>* q = p;
            p = p->next;

            delete q;
        }

        delete lit->second;
    }

}

template<class T>
void NonInterSect<T>::prTlist(LinkNode<T>* head)
{
    LinkNode<T>* p= head;

    while(p != NULL)
    {
        cout<<p->val<<",";
        p = p->next;
    }

    cout<<endl;
}

template<class T>
void NonInterSect<T>::prTset()
{
    typename map<T, LinkList<T>* >::iterator lit;

    for(lit = linkmap.begin(); lit != linkmap.end(); ++lit)
    {
        prTlist(lit->second->head);
    }
}

template<class T>
void NonInterSect<T>::make_set(T val)
{
    //检查对象是否存在,如果存在,则不做操作
    if (nodemap.count(val))
    {
        return ;
    }

    //create a linknode
    LinkNode<T>* pnode = new LinkNode<T>;

    pnode->val = val;
    pnode->next = NULL;
    pnode->repr = pnode;

    //create a linklist
    LinkList<T> * list = new LinkList<T>;
    list->head = pnode;
    list->tail = pnode;
    list->size = 1;

    //创建map联系
    nodemap[val] = pnode;
    linkmap[val] = list;
}

template<class T>
LinkNode<T>* NonInterSect<T>::find_set(T val)
{
    if (nodemap.count(val))
    {
        //应该返回代表元素的地址
        return nodemap[val]->repr;
    }

    return NULL;
}

template<class T>
void NonInterSect<T>::update_repr(LinkNode<T>* head, LinkNode<T> * repr)
{
    LinkNode<T>* p= head;

    while(p != NULL)
    {
        p->repr = repr;
        p = p->next;
    }
}

template<class T>
void NonInterSect<T>::union_set(T u, T v)
{
    //check if they are in the same list
    if (!nodemap.count(u) || !nodemap.count(v) || nodemap[u] == nodemap[v])
    {
        return ;
    }

    //union two list. find the shortest link, then merge to longer link.
    T repr_val_u = nodemap[u]->repr->val;
    T repr_val_v = nodemap[v]->repr->val;
    LinkList<T> * p_link_u = linkmap[repr_val_u];
    LinkList<T> * p_link_v = linkmap[repr_val_v];

    if (p_link_u->size <= p_link_v->size)
    {
        //合并长度短的u链表到v链表中去。如何合并?见下面分析
        p_link_v->tail->next = nodemap[u]->repr;  //合并完毕,只要将v链表的尾节点指向u的代表节点即可
        p_link_v->size += p_link_u->size;
        p_link_v->tail = p_link_u->tail;  //修改v链表的尾节点

        //接下来,修改u的链表中的每个节点的代表节点。这是一个遍历过程,所以我们要选择长度短的作为并合并的对象
        update_repr(nodemap[u]->repr, nodemap[v]->repr);

        linkmap.erase(repr_val_u);
        delete p_link_u;
    }
    else
    {
        p_link_u->tail->next = nodemap[v]->repr;  //合并完毕,只要将v链表的尾节点指向u的代表节点即可
        p_link_u->size += p_link_v->size;
        p_link_u->tail = p_link_v->tail;  //修改v链表的尾节点

        update_repr(nodemap[v]->repr, nodemap[u]->repr);

        linkmap.erase(repr_val_v);
        delete p_link_v;
    }
}

int main()
{
    NonInterSect<char> nonTer;

    /*
    for(int i = 1; i <= 5; ++i)
    {
        nonTer.make_set(i);
    }
    */

    for(char i = 'a'; i <= 'e'; ++i)
    {
        nonTer.make_set(i);
    }

    nonTer.prTset();
    
    //LinkNode<int>* target = nonTer.find_set(1);
    LinkNode<char>* target = nonTer.find_set('a');
    cout<<"代表元素是:"<<target->val<<endl;

    //nonTer.union_set(1,2);
    nonTer.union_set('a','b');

    nonTer.prTset();

    //target = nonTer.find_set(1);
    target = nonTer.find_set('a');
    cout<<"代表元素是:"<<target->val<<endl;

    //nonTer.union_set(1,4);
    nonTer.union_set('a','d');

    nonTer.prTset();

    return 0;
}
类型是int时,运行效果如下图1:


                    

                            图1-int类型程序结果

类型是char时,运行效果如下图2:

                

                    图2-char类型程序结果




评论

发表评论