Какие операции могут быть выполнены на непересекающихся наборах?
Я просто изучил непересекающуюся структуру данных набора, и я знаю, что это также называют, "находят объединение, что структуры данных", объединение и находка являются двумя основными операциями этой структуры данных. Мы можем, может выполнить объединение на непересекающихся наборах, так же мы можем выполнить, находят операции; я хочу знать то, что другие операции мы можем выполнить на непересекающихся наборах кроме объединения и найти.
3 ответа
Структура непересекающихся множеств также называется «структурой объединения-поиска». Поэтому операции union , find и MakeSet должны поддерживаться в любом случае. Вся эта структура не в других операциях, и то, поддерживаются ли они, зависит от реализации и ваших целей. Иногда вам нужно выбрать конкретную реализацию специально для того, чтобы удовлетворить потребности вашего проекта в дополнительных операциях.
В остальном было бы неплохо, если бы мы поддерживали другие основные операции, связанные с наборами. Пронумеруем их:
- пересечение двух множеств. Поскольку множества не пересекаются, он всегда пуст, если эти два набора не совпадают.
- объединение двух наборов - поддерживается из коробки.
- получить элемент из набора - поддерживается, это, скорее всего, результат
find. - удалить элемент из набора - зависит от реализации. Когда наборы реализованы как леса, это сложно и требует более медленных дополнительных операций. Когда наборы реализованы в виде связанных списков, это просто.
- перечисляет набор , т.е. повторяет каждый элемент в данном наборе. Это снова зависит от реализации: для связанных списков это просто, для реализации, подобной лесу, требуются дополнительные структуры для поддержки.
При использовании ванильной структуры данных union-find вы не можете перечислить фактический набор, поэтому многие операции над наборами недоступны. Это связано с тем, что в ванильной версии у вас есть указатели только в одном направлении --- на рисунке ниже каждая диагональная линия соответствует стрелке вверх, а корни (верхняя линия) являются корневыми объектами для наборов:
o [set1] o [Set2]
/ \ \
o o o
/
o
Итак невозможно найти все объекты, скажем, набора 1; например, вы не можете отследить пути к ним от корневого узла. У вас также могут быть указатели вниз, но это значительно усложняет структуру данных, поскольку объект может иметь произвольное количество родителей в структуре данных.
Таким образом, это в основном для следующих операций:
- Ответ: принадлежат ли мои объекты A и B к одному набору или нет?
- Объединить наборы S1 и S2, чтобы все объекты в наборах теперь рассматривались принадлежать к одному и тому же набору
Чтобы уточнить это, структура данных набора объединения имеет очень низкую временную сложность для операций, которые она поддерживает; оба слияния наборов и ответ на один и тот же запрос занимают амортизированное постоянное время (O (1)); из-за этой самой временной сложности вы не можете поддерживать все заданные операции. Например, стандартное представление множества - это [двоичное] дерево поиска, где большинство операций имеют как минимум O (log n) сложность.
Смысл структуры непересекающегося множества объединение-поиск не столько в выполнении элементарных операций над множеством, как кажется, предполагают ваш вопрос и другие респонденты. Вместо этого речь идет о высокоэффективной реализации структуры, которая нужна определенным алгоритмам. В частности, поиск связных компонентов и минимальных остовных деревьев строит их наиболее эффективные реализации на основе непересекающихся множеств с поиском по объединению.