Внедрение несвязанных наборов (поиск соединения) в С++
Я пытаюсь реализовать 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;, Теперь у этих Узлов есть только указатели на своих родителей, поэтому я не уверен, как найти дно дерева. Как я смогу пройти мои деревья, чтобы освободить их всех?
Я понимаю основную концепцию этой структуры данных, но я немного запутался в реализации. Любые советы и предложения были бы очень желанными, спасибо.
Ответы
Ответ 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
Ответ 2
Boost имеет реализацию непересекающихся множеств:
http://www.boost.org/doc/libs/1_54_0/libs/disjoint_sets/disjoint_sets.html
Ответ 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, чтобы проверить, находятся ли эти узлы одновременно в вашем подграфе. Если они есть, вы можете перейти к следующему краю. В противном случае пришло время добавить это ребро к вашему подграфу и выполнить операцию объединения между двумя вершинами, связанными с этим ребром.
Ответ 6
В этой статье в блоге показана реализация С++ с использованием сжатия пути:
http://toughprogramming.blogspot.com/2013/04/implementing-disjoint-sets-in-c.html
Ответ 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) или так я прочитал.
пс. проверьте, что я написал, хотя я уверен, что это правильно.