在C++中实现不相交集(Union Find)

Question

我正在尝试实现Disjoint Sets以用于Kruskal的算法,但我无法准确理解它应该如何完成,特别是如何管理树林.在阅读了维基百科关于不相交集的描述之后,在阅读了算法导论(Cormen等人)中的描述后,我得出以下结论:

    class DisjointSet
    {
    public:
        class   Node 
        {
        public:
            int         data;
            int         rank;

            Node*       parent;

            Node() : data(0), 
                     rank(0),
                     parent(this) { } // the constructor does MakeSet
        };

        Node*   find(Node*);
        Node*   merge(Node*, Node*); // Union
    };


    DisjointSet::Node*   DisjointSet::find(DisjointSet::Node* n)
    {
        if (n != n->parent) {
            n->parent = find(n->parent);
        }
        return n->parent;
    }

    DisjointSet::Node* DisjointSet::merge(DisjointSet::Node* x,
                                          DisjointSet::Node* y)
    {
        x = find(x);
        y = find(y);

        if (x->rank > y->rank) {
            y->parent = x;
        } else {
            x->parent = y;
            if (x->rank == y->rank) {
                ++(y->rank);
            }
        }
    }

我很确定这是不完整的,我错过了一些东西.

算法简介提到应该有一片树林,但它没有给出这片林的实际实施的任何解释.我观看了CS 61B第31讲:不相交集(http://www.youtube.com/watch?v=wSPAjGfDl7Q),讲师只使用一个数组来存储森林及其所有树和值.我提到的没有明确的'Node'类型.我还发现了许多其他来源(我不能发布多个链接),这也使用了这种技术.我很乐意这样做,除了这依赖于数组的索引进行查找,因为我想存储除int之外的类型的值,我需要使用其他东西(std :: map可以想到).

我不确定的另一个问题是内存分配,因为我使用的是C++.我存储指针树,我的MakeSet操作将是:new DisjointSet :: Node; .现在,这些节点只有指向父母的指针,所以我不确定如何找到树的底部.我怎样才能遍历我的树木以解除所有这些？

我理解这个数据结构的基本概念,但我对实现有点困惑.非常欢迎任何意见和建议,谢谢.

Answer 1

我不能谈论该算法，但对于内存管理，通常您会使用称为智能指针的东西，它将释放它所指向的内容。您可以获得共享所有权和单一所有权智能指针，也可以获得非所有权。正确使用这些将保证不会出现内存问题。