Реализация непересекающихся множеств (Union Find) в C ++

Question

Я пытаюсь реализовать дизъюнктные множества для использования в алгоритме Крускала, но у меня возникают проблемы с пониманием, как именно это должно быть сделано и, в частности, как управлять лесом деревьев. После прочтения описания непересекающихся множеств в Википедии и прочтения описания в разделе Введение в алгоритмы (Кормен и др.) Я пришел к следующему:

    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

Не идеальная реализация каким-либо образом (я все-таки написал это!), Но поможет ли это?

/***
 * millipede: DisjointSetForest.h
 * Copyright Stuart Golodetz, 2009. All rights reserved.
 ***/

#ifndef H_MILLIPEDE_DISJOINTSETFOREST
#define H_MILLIPEDE_DISJOINTSETFOREST

#include <map>

#include <common/exceptions/Exception.h>
#include <common/io/util/OSSWrapper.h>
#include <common/util/NullType.h>

namespace mp {

/**
@brief  A disjoint set forest is a fairly standard data structure used to represent the partition of
        a set of elements into disjoint sets in such a way that common operations such as merging two
        sets together are computationally efficient.

This implementation uses the well-known union-by-rank and path compression optimizations, which together
yield an amortised complexity for key operations of O(a(n)), where a is the (extremely slow-growing)
inverse of the Ackermann function.

The implementation also allows clients to attach arbitrary data to each element, which can be useful for
some algorithms.

@tparam T   The type of data to attach to each element (arbitrary)
*/
template <typename T = NullType>
class DisjointSetForest
{
    //#################### NESTED CLASSES ####################
private:
    struct Element
    {
        T m_value;
        int m_parent;
        int m_rank;

        Element(const T& value, int parent)
        :   m_value(value), m_parent(parent), m_rank(0)
        {}
    };

    //#################### PRIVATE VARIABLES ####################
private:
    mutable std::map<int,Element> m_elements;
    int m_setCount;

    //#################### CONSTRUCTORS ####################
public:
    /**
    @brief  Constructs an empty disjoint set forest.
    */
    DisjointSetForest()
    :   m_setCount(0)
    {}

    /**
    @brief  Constructs a disjoint set forest from an initial set of elements and their associated values.

    @param[in]  initialElements     A map from the initial elements to their associated values
    */
    explicit DisjointSetForest(const std::map<int,T>& initialElements)
    :   m_setCount(0)
    {
        add_elements(initialElements);
    }

    //#################### PUBLIC METHODS ####################
public:
    /**
    @brief  Adds a single element x (and its associated value) to the disjoint set forest.

    @param[in]  x       The index of the element
    @param[in]  value   The value to initially associate with the element
    @pre
        -   x must not already be in the disjoint set forest
    */
    void add_element(int x, const T& value = T())
    {
        m_elements.insert(std::make_pair(x, Element(value, x)));
        ++m_setCount;
    }

    /**
    @brief  Adds multiple elements (and their associated values) to the disjoint set forest.

    @param[in]  elements    A map from the elements to add to their associated values
    @pre
        -   None of the elements to be added must already be in the disjoint set forest
    */
    void add_elements(const std::map<int,T>& elements)
    {
        for(typename std::map<int,T>::const_iterator it=elements.begin(), iend=elements.end(); it!=iend; ++it)
        {
            m_elements.insert(std::make_pair(it->first, Element(it->second, it->first)));
        }
        m_setCount += elements.size();
    }

    /**
    @brief  Returns the number of elements in the disjoint set forest.

    @return As described
    */
    int element_count() const
    {
        return static_cast<int>(m_elements.size());
    }

    /**
    @brief  Finds the index of the root element of the tree containing x in the disjoint set forest.

    @param[in]  x   The element whose set to determine
    @pre
        -   x must be an element in the disjoint set forest
    @throw Exception
        -   If the precondition is violated
    @return As described
    */
    int find_set(int x) const
    {
        Element& element = get_element(x);
        int& parent = element.m_parent;
        if(parent != x)
        {
            parent = find_set(parent);
        }
        return parent;
    }

    /**
    @brief  Returns the current number of disjoint sets in the forest (i.e. the current number of trees).

    @return As described
    */
    int set_count() const
    {
        return m_setCount;
    }

    /**
    @brief  Merges the disjoint sets containing elements x and y.

    If both elements are already in the same disjoint set, this is a no-op.

    @param[in]  x   The first element
    @param[in]  y   The second element
    @pre
        -   Both x and y must be elements in the disjoint set forest
    @throw Exception
        -   If the precondition is violated
    */
    void union_sets(int x, int y)
    {
        int setX = find_set(x);
        int setY = find_set(y);
        if(setX != setY) link(setX, setY);
    }

    /**
    @brief  Returns the value associated with element x.

    @param[in]  x   The element whose value to return
    @pre
        -   x must be an element in the disjoint set forest
    @throw Exception
        -   If the precondition is violated
    @return As described
    */
    T& value_of(int x)
    {
        return get_element(x).m_value;
    }

    /**
    @brief  Returns the value associated with element x.

    @param[in]  x   The element whose value to return
    @pre
        -   x must be an element in the disjoint set forest
    @throw Exception
        -   If the precondition is violated
    @return As described
    */
    const T& value_of(int x) const
    {
        return get_element(x).m_value;
    }

    //#################### PRIVATE METHODS ####################
private:
    Element& get_element(int x) const
    {
        typename std::map<int,Element>::iterator it = m_elements.find(x);
        if(it != m_elements.end()) return it->second;
        else throw Exception(OSSWrapper() << "No such element: " << x);
    }

    void link(int x, int y)
    {
        Element& elementX = get_element(x);
        Element& elementY = get_element(y);
        int& rankX = elementX.m_rank;
        int& rankY = elementY.m_rank;
        if(rankX > rankY)
        {
            elementY.m_parent = x;
        }
        else
        {
            elementX.m_parent = y;
            if(rankX == rankY) ++rankY;
        }
        --m_setCount;
    }
};

}

#endif

Answer 2

ваша реализация выглядит хорошо (кроме функции слияния вы должны либо объявить возвращение void, либо поместить туда возврат, я предпочитаю возвращать void). Дело в том, что вам нужно отслеживать Nodes*. Вы можете сделать это, имея vector<DisjointSet::Node*> в своем классе DisjointSet или имея это vector в другом месте и объявив методы DisjointSet как static.

Вот пример выполнения (обратите внимание, что я изменил слияние, чтобы вернуть void, и не изменил методы DisjointSet на static:

int main()
{
    vector<DisjointSet::Node*> v(10);
    DisjointSet ds;

    for (int i = 0; i < 10; ++i) {
        v[i] = new DisjointSet::Node();
        v[i]->data = i;
    }

    int x, y;

    while (cin >> x >> y) {
        ds.merge(v[x], v[y]);
    }

    for (int i = 0; i < 10; ++i) {
        cout << v[i]->data << ' ' << v[i]->parent->data << endl;
    }

    return 0;
}

С этим входом:

3 1
1 2
2 4
0 7
8 9

Он печатает ожидаемое:

0 7
1 1
2 1
3 1
4 1
5 5
6 6
7 7
8 9
9 9

Ваш лес состоит из деревьев:

   7    1       5    6   9
 /    / | \              |
0    2  3  4             8

Итак, ваш алгоритм хорош, имейте лучшую сложность для Union-find, насколько я знаю, и вы отслеживаете свои Node s на своем vector. Так что вы можете просто освободить:

for (int i = 0; i < int(v.size()); ++i) {
    delete v[i];
}

Answer 3

Boost имеет реализацию несвязанного множества:

http://www.boost.org/doc/libs/1_54_0/libs/disjoint_sets/disjoint_sets.html

Answer 4

Я не могу говорить об алгоритме, но для управления памятью, как правило, вы будете использовать то, что называется умным указателем, который освободит то, на что он указывает. Вы можете получить интеллектуальные указатели совместного владения и единоличного владения, а также отсутствие права собственности. Правильное их использование гарантирует отсутствие проблем с памятью.

Answer 5

Если вы пытаетесь спросить, какой стиль лучше для реализации непересекающегося множества (вектор или карта (дерево rb)), то я могу кое-что добавить

1. make_set (int key , node info ): обычно это функция-член, которая (1) добавляет узел и (2) заставляет узел указывать на себя (parent = key), это изначально создает непересекающийся набор. сложность времени работы для вектора O (n), для карты O (n * logn).
2. find_set( int key ): обычно это две функции: (1) поиск узла по заданному ключу (2) сжатие пути. Я не мог действительно рассчитать его для сжатия пути, но для простого поиска узла, временной сложности для (1) вектора O (1) и (2) карты O (log (n)).

В заключение я хотел бы сказать, что, хотя, глядя здесь, реализация вектора выглядит лучше, временные сложности обоих O (M * α (n)) ≈ O (M * 5) или около того, что я прочитал.

пс. проверьте, что я написал, хотя я уверен, что это правильно.

Answer 6

Следующий код, по-видимому, прост для понимания при реализации наборов несоответствий find-find путем сжатия путей

int find(int i)
{
    if(parent[i]==i)
    return i;
    else
    return parent[i]=find(parent[i]);
}
void union(int a,int b)
{
    x=find(a);y=find(b);
        if(x!=y)
        {
            if(rank[x]>rank[y])
            parent[y]=x;
            else
            {
            parent[x]=y;
            if(rank[x]==rank[y])
            rank[y]+=1;             
            }
        }
}

Answer 7

Для реализации Непересекающихся множеств с нуля, я настоятельно рекомендую прочитать книгу Структуры данных и анализ алгоритмов в C ++ Марк А. Вайс .

В главе 8 он начинается с базового поиска / объединения, затем постепенно добавляет объединение по высоте / глубине / рангу и находит сжатие.В конце концов, он предоставляет анализ Big-O.

Поверьте мне, в нем есть все, что вы хотите знать о несвязанных множествах и его реализации на C ++.

Answer 8

Посмотрите на этот код

class Node {
    int id,rank,data;
    Node *parent;

public :

    Node(int id,int data) {
        this->id = id;
        this->data = data;
        this->rank =0;
        this->parent = this;
    }

    friend class DisjointSet;
};

class DisjointSet {
    unordered_map<int,Node*> forest;

    Node *find_set_helper(Node *aNode) {
        if( aNode->parent != aNode)
            aNode->parent = find_set_helper(aNode->parent);

        return aNode->parent;
    }

    void link(Node *xNode,Node *yNode) {
        if( xNode->rank > yNode->rank)
            yNode->parent = xNode;
        else if(xNode-> rank < yNode->rank)
            xNode->parent = yNode;
        else {
            xNode->parent = yNode;
            yNode->rank++;
        }
    }

public:
    DisjointSet() {

    }

    void make_set(int id,int data) {
        Node *aNode = new Node(id,data);
        this->forest.insert(make_pair(id,aNode));
    }

    void Union(int xId, int yId) {
        Node *xNode = find_set(xId);
        Node *yNode = find_set(yId);

        if(xNode && yNode)
            link(xNode,yNode);
    }

    Node* find_set(int id) {
        unordered_map<int,Node*> :: iterator itr = this->forest.find(id);
        if(itr == this->forest.end())
            return NULL;

        return this->find_set_helper(itr->second);
    }

    void print() {
        unordered_map<int,Node*>::iterator itr;
        for(itr = forest.begin(); itr != forest.end(); itr++) {
            cout<<"\nid : "<<itr->second->id<<"  parent :"<<itr->second->parent->id;
        }
    }

    ~DisjointSet(){
        unordered_map<int,Node*>::iterator itr;
        for(itr = forest.begin(); itr != forest.end(); itr++) {
            delete (itr->second);
        }
    }

};

Answer 9

В этой статье блога показана реализация C ++ с использованием сжатия пути: http://toughprogramming.blogspot.com/2013/04/implementing-disjoint-sets-in-c.html

Answer 10

Ваша реализация в порядке. Все, что вам теперь нужно сделать, это сохранить массив непересекающихся наборов узлов, чтобы вы могли вызывать на них методы union / find.

Для алгоритма Крускала вам понадобится массив, содержащий один узел с несвязным множеством на вершину графа. Затем, когда вы будете искать следующий край для добавления в ваш подграф, вы будете использовать метод find, чтобы проверить, есть ли эти узлы в вашем подграфе. Если они есть, то вы можете перейти к следующему краю. В противном случае, пришло время добавить этот ребро в ваш подграф и выполнить операцию объединения двух вершин, соединенных этим ребром.