Система непересекающихся множеств
Свойства и структура алгоритма
Общее описание алгоритма
Система непересекающихся множеств[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] процессорах, однако не может использоваться как онлайн-алгоритм.
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
- ↑ 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.