подходящая структура данных для разбиения множества (графика)

Question

Мне нужно хранить узлы группировки данных в разделе графа, что-то вроде:

[узел1, узел2] [узел3] [узел4, узел5, узел6]

Моя первая идея состояла в том, чтобы иметь просто простой вектор или массив целых чисел, где позиция в массиве обозначена как node_id, а ее значением является своего рода group_id

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

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

Есть предложения?

Answer 1

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

Реализация на C ++ доступна в Boost .

Answer 2

На ум приходят две хорошие структуры данных.

Первая структура данных (и та, что упоминалась здесь ранее) - это лес с несвязным множеством, который дает чрезвычайно эффективные реализации "слияния этих двух".наборы "и" какой набор х в? ".Однако он не поддерживает операцию разделения групп друг от друга.

Другая структура, которую я бы порекомендовал - это дерево ссылок / вырезок.Эта структура позволяет создавать разделы графа, которые можно объединять в деревья.В отличие от леса непересекающихся множеств, дерево, описывающее раздел, можно разрезать на более мелкие деревья, что позволяет разбивать разделы на более мелкие группы.Эта структура немного менее эффективна, чем структура union / find, но она все еще поддерживает все операции в амортизированном O (lg n).