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

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

Использование

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

Определение

Пусть $S$ конечное множество, разбитое на непересекающиеся классы $X_i$:

$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$.

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

• MakeSet($x$): создает для элемента $x$ новый класс. Назначает этот же элемент представителем созданного класса.
• Union($r$, $s$): объединяет оба класса, принадлежащие представителям $r$ и $s$, и назначает $r$ представителем нового класса.
• Find($x$): определяет для $x \in S$ класс к которому принадлежит элемент, и возвращает его представителя.

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

Тривиальная реализация сохраняет принадлежность элементов из $S$ и представителей $r_i$ в индексном массиве. На практике же, чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Find. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.

• Union($r$, $s$): Вешает корень более низкого дерева под корень более высокого дерева. Если при этом $r$ становится ребенком $s$, оба узла меняются местами.
• Find($x$): проходит путь от $x$ до корня дерева и возвращает его (корень в данном случае является представителем).

Эвристики

Для ускорения операций Union и Find используются следующие эвристики.

Union-By-Size

Во время операции Union(r, s) корень более низкого дерева вешается под корень более высокого дерева. Благодаря этому подходу сохраняется балансировка дерева. Глубина каждого поддерева T не может превысить величину $\log \left|T\right|$. При использовании этой эвристики worst-case-время операции Find уменьшается с $O(n)$ до $O(\log n)$. Для эффективной реализации предлагается сохранять в корне количество узлов в дереве.

Random Union

Однако можно и не тратить дополнительные $O(n)$ памяти на сохранение количества узлов в дереве. Достаточно выбирать корень случайным образом — как ни удивительно, такое решение дает на случайных запросах скорость, вполне сравнимую с реализацией, описанной выше. Тем не менее, если имеется много запросов вида "объединить большое множество с маленьким", данная эвристика улучшает матожидание (т.е. среднее время работы) всего в два раза, поэтому использовать её без эвристики сжатия путей не рекомендуется.

Сжатие путей

Используется чтобы ускорить операцию Find($x$). При каждом новом поиске, все элементы находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция Find будет работать в среднем α(n), где α - функция, обратная функции Аккермана. Это позволяет значительно ускорить работу, так как α для всех применяемых на практике значений принимает значение, меньшее 5.

Пример реализации

Реализация на C++

const int MAXN = 1000;
 
int p[MAXN], rank[MAXN];
 
void MakeSet(int x) {
    p[x] = x;
    rank[x] = 0;
}
 
int Find(int x) {
    return ( x == p[x] ? x : p[x] = Find(p[x]) );
}
 
void Union(int x, int y) {
    if ( (x = Find(x)) == (y = Find(y)) )
        return;
 
    if ( rank[x] <  rank[y] )
        p[x] = y;
    else
        p[y] = x;
 
    if ( rank[x] == rank[y] )
        ++rank[x];
}

Реализация на Free Pascal

procedure makeset(x:integer);
begin
 a[x]:=x;
end;
 
function find(x:integer):integer;
begin
if a[x]<>x then begin a[x]:=find(a[x]); end;
find:=a[x];
end;
 
procedure union(x,y:integer);
begin
randomize;
x:=find(x);
y:=find(y);
if x<>y then
if random <= 0.5 then a[x]:=y else a[y]:=x;
end;

Ссылки

• Реализация системы непересекающихся множеств на Java
• Система непересекающихся множеств на сайте e-maxx.ru
• Система непересекающихся множеств на сайте habrahabr.ru