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

Question

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

[узел1, узел2] [node3] [node4, node5, node6]

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

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

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

Любые предложения?

Answer 1

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

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

Answer 2

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

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

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