Какие операции можно выполнить на непересекающихся множествах?

Question

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

Answer 1

Структура непересекающихся множеств также называется «структурой объединения-поиска». Поэтому операции union, find и MakeSet должны поддерживаться в любом случае. Другие операции - не то, для чего предназначена эта структура, и то, поддерживаются ли они, зависит от реализации и ваших целей. Иногда вам нужно будет выбрать конкретную реализацию специально для удовлетворения потребностей вашего проекта в дополнительных операциях.

Кроме того, было бы неплохо, если бы мы поддерживали другие основные операции, связанные с множествами. Давайте перечислим их:

• пересечение из двух комплектов. Поскольку множества не пересекаются, оно всегда пусто, если только эти два множества не совпадают.
• объединение из двух комплектов - поддерживается из коробки.
• получить элемент из набора - поддерживается, скорее всего, это результат find.
• удалить элемент из набора - зависит от реализации. Когда наборы реализованы как леса, это сложно и требует более медленных дополнительных операций. Когда наборы реализованы в виде связанных списков, это просто.
• перечислить набор , то есть выполнить итерацию каждого элемента в данном наборе. Это снова зависит от реализации: для связанных списков это просто, для лесоподобной реализации требуется поддержка дополнительных структур.

Answer 2

С помощью структуры данных vanilla union-find вы не можете перечислить фактический набор, так как многие из операций набора недоступны. Это потому, что в ванильной версии у вас есть только указатели в одном направлении - на рисунке ниже каждая диагональная линия соответствует стрелке вверх, а корни (верхняя линия) являются корневыми объектами для наборов:

     o [set1]         o [Set2]
    / \                \
   o   o                o
  /
 o

Так что нет способа найти все объекты, скажем, множества 1; например, вы не можете отследить пути к ним от корневого узла. Вы также можете иметь указатели вниз, но это значительно усложняет структуру данных, потому что объект может иметь произвольное количество родителей в структуре данных.

Так что это действительно в основном для следующих операций:

• Ответ на вопрос: принадлежат ли мои объекты A и B одному и тому же набору или нет?
• Объединение наборов S1 и S2 так, чтобы все объекты в наборах теперь считались принадлежащими одному и тому же набору

Чтобы уточнить это, структура данных с объединенным набором имеет очень низкую временную сложность для операций, которые она поддерживает; и объединение наборов, и ответ на один и тот же набор запросов занимают амортизированное постоянное время (O (1)); из-за этой временной сложности вы не можете поддерживать все операции над множествами. Например, стандартное представление набора представляет собой [двоичное] дерево поиска, где большинство операций имеют по меньшей мере O (log n) сложностей.

Answer 3

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