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

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

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

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

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

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

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

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

1.8 Ресурс параллелизма алгоритма

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

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