Система непересекающихся множеств

Свойства и структура алгоритмов

Общее описание алгоритма

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

Названия на английском языке – Union-Find Data Structure, Disjoint-Set Data Structure, Merge-Find- Set.

Систему непересекающихся множеств можно применить при решении следующих задач:

• поиск компонент связности графа за время [math]\displaystyle{ O(m \alpha(m, n) }[/math];
• восстановление отношения эквивалентности по его части;
• поддержание информации о текущих фрагментах графа в алгоритмах построения минимального остовного дерева.

Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым поиск в ширину (который решает ту же задачу о компонентах связности за линейное время [math]\displaystyle{ O(m) }[/math]).

Описание ресурса параллелизма алгоритма

Система непересекающихся множеств допускает эффективную многопоточную реализацию в виде неблокирующего алгоритма «без ожидания».

Параллельный алгоритм Шилоаха-Вишкина использует аналогичную структуру данных и находит компоненты связности за время [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ n + 2m }[/math] процессорах, однако не может использоваться как онлайн-алгоритм.

Программная реализация алгоритмов

Существующие реализации алгоритма

• Boost Graph Library (функция incremental_components).