Система непересекающихся множеств
Система непересекающихся множеств — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: [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] до корня дерева и возвращает его (корень в данном случае является представителем).
