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

Система непересекающихся множеств — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: [math]\displaystyle{ \{\mathrm{Union}, \mathrm{Find}, \mathrm{MakeSet}\} }[/math].

Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.

Определение

Пусть [math]\displaystyle{ S }[/math] конечное множество, разбитое на непересекающиеся подмножества (классы) [math]\displaystyle{ X_i }[/math]:

[math]\displaystyle{ S = X_0 \cup X_1 \cup X_2 \cup \ldots \cup X_k: X_i \cap X_j = \varnothing \quad\forall i, j \in \lbrace 0, 1, \ldots, k \rbrace, i \neq j }[/math].

Каждому подмножеству [math]\displaystyle{ X_i }[/math] назначается представитель [math]\displaystyle{ r_i \in X_i }[/math]. Соответствующая система непересекающихся множеств поддерживает следующие операции:

• [math]\displaystyle{ \mathrm{MakeSet}(x) }[/math]: создаёт для элемента [math]\displaystyle{ x }[/math] новое подмножество. Назначает этот же элемент представителем созданного подмножества.
• [math]\displaystyle{ \mathrm{Union}(r, s) }[/math]: объединяет оба подмножества, принадлежащие представителям [math]\displaystyle{ r }[/math] и [math]\displaystyle{ s }[/math], и назначает [math]\displaystyle{ r }[/math] представителем нового подмножества.
• [math]\displaystyle{ \mathrm{Find}(x) }[/math]: определяет для [math]\displaystyle{ x \in S }[/math] подмножество, к которому принадлежит элемент, и возвращает его представителя.

Алгоритмическая реализация

Тривиальная реализация сохраняет принадлежность элементов из [math]\displaystyle{ S }[/math] и представителей [math]\displaystyle{ r_i }[/math] в индексном массиве. На практике же чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Шаблон:Math. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.

• [math]\displaystyle{ \mathrm{Union}(r, s) }[/math]: вешает корень более низкого дерева под корень более высокого дерева. Если при этом [math]\displaystyle{ r }[/math] становится потомком [math]\displaystyle{ s }[/math], оба узла меняются местами.
• [math]\displaystyle{ \mathrm{Find}(x) }[/math]: проходит путь от [math]\displaystyle{ x }[/math] до корня дерева и возвращает его (корень в данном случае является представителем).

Эвристики

Для ускорения операций Шаблон:Math и Шаблон:Math могут быть использованы эвристики Шаблон:Math, Шаблон:Math, Шаблон:Math и сжатие путей.

В эвристике Шаблон:Math во время операции [math]\displaystyle{ \mathrm{Union}(r, s) }[/math] корень меньшего дерева вешается под корень большего дерева. Благодаря этому подходу сохраняется балансировка дерева. Глубина каждого поддерева [math]\displaystyle{ T }[/math] не может превысить величину [math]\displaystyle{ \log \left|T\right| }[/math]. При использовании этой эвристики время операции Шаблон:Math в худшем случае увеличивается с [math]\displaystyle{ O(\log n) }[/math] до [math]\displaystyle{ O(n) }[/math]. Для эффективной реализации предлагается сохранять в корне количество узлов в дереве.

Эвристика Шаблон:Math аналогична Шаблон:Math, но использует высоту дерева вместо размера.

В эвристике Шаблон:Math используется тот факт, что можно не тратить дополнительные [math]\displaystyle{ O(n) }[/math] памяти на сохранение количества узлов в дереве: достаточно выбирать корень случайным образом — такое решение даёт на случайных запросах скорость, вполне сравнимую с другими реализациями. Тем не менее, если имеется много запросов вида «объединить большое множество с маленьким», данная эвристика улучшает матожидание (то есть среднее время работы) всего в два раза, поэтому использовать её без эвристики сжатия путей не рекомендуется.

Эвристика сжатия путей используется, чтобы ускорить операцию [math]\displaystyle{ \mathrm{Find}(x) }[/math]. При каждом новом поиске все элементы, находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция Шаблон:Math будет работать в среднем [math]\displaystyle{ \alpha(n) }[/math], где [math]\displaystyle{ \alpha }[/math] — функция, обратная функции Аккермана. Это позволяет значительно ускорить работу, так как [math]\displaystyle{ \alpha }[/math] для всех применяемых на практике значений принимает значение, меньшее 5.