Система непересекающихся множеств
Свойства и структура алгоритмов
Общее описание алгоритма
Система непересекающихся множеств[1] представляет собой структуру данных и сопутствующие алгоритмы для хранения информации об элементах, объединённых в одно или несколько множеств. Алгоритмы позволяют указать, что два элемента находятся в одном и том же множестве, а также узнать, какому множеству принадлежит данный элемент (например, чтобы проверить, принадлежат ли два данных элемента одному и тому же множеству).
Названия на английском языке – Union-Find Data Structure, Disjoint-Set Data Structure, Merge-Find Set.
Систему непересекающихся множеств можно применить при решении следующих задач:
- поиск компонент связности графа за время [math]\displaystyle{ O(m \alpha(m, n) }[/math];
- восстановление отношения эквивалентности по его части;
- поддержание информации о текущих фрагментах графа в алгоритмах построения минимального остовного дерева.
Система непересекающихся множеств может использоваться как онлайн-алгоритм, когда перемежаются запросы на объединение множеств и на определение множества по элементу. По этой причине этому подходу часто отдаётся предпочтение перед асимптотически более быстрым поиск в ширину (который решает ту же задачу о компонентах связности за линейное время [math]\displaystyle{ O(m) }[/math]).
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Описание ресурса параллелизма алгоритма
Система непересекающихся множеств допускает эффективную многопоточную реализацию [2] в виде неблокирующего алгоритма «без ожидания».
Параллельный алгоритм Шилоаха-Вишкина использует аналогичную структуру данных и находит компоненты связности за время [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ n + 2m }[/math] процессорах, однако не может использоваться как онлайн-алгоритм.
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Boost Graph Library (функция
incremental_components). - Java: JGraphT (класс UnionFind).
Литература
- ↑ Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.
- ↑ Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.