Подтвердить что ты не робот

Внедрение несвязанных наборов (поиск соединения) в С++

Я пытаюсь реализовать Disjoint Sets для использования в алгоритме Kruskal, но мне трудно понять, как это должно быть сделано, и в частности, как управлять лесом деревьев. После прочтения Википедического описания Disjoint Sets и после прочтения описания во Введении в Алгоритмы (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 Lecture 31: Disjoint Sets (http://www.youtube.com/watch?v=wSPAjGfDl7Q), и здесь лектор использует только массив для хранения как леса, так и всех его деревьев и значения. Не существует явного типа класса Node, как я уже упоминал. Я также нашел много других источников (я не могу разместить более одной ссылки), которые также используют эту технику. Я был бы рад сделать это, за исключением того, что это зависит от индексов массива для поиска, и поскольку я хочу хранить значения типа, отличного от int, мне нужно использовать что-то еще (std:: map приходит на ум).

Другая проблема, о которой я не уверен, - это распределение памяти, потому что я использую С++. Я храню деревья указателей, и моя операция MakeSet будет: new DisjointSet:: Node;, Теперь у этих Узлов есть только указатели на своих родителей, поэтому я не уверен, как найти дно дерева. Как я смогу пройти мои деревья, чтобы освободить их всех?

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

4b9b3361

ОТВЕТЫ

Ответ 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

Ответ 3

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

Ответ 4

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

Вот пример запуска (обратите внимание, что я сменил merge для возврата 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 на своем vector. Таким образом, вы можете просто освободить:

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

Ответ 5

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

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

Ответ 7

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

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);
        }
    }

};

Ответ 8

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

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

Поверьте мне, у него есть все, что вы хотите знать о Disjoint Sets и его реализации на С++.

Ответ 9

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

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;             
            }
        }
}

Ответ 10

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

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

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

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