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

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

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

Определение

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

.

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

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

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

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

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

Эвристики

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

Union-By-Size

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

Union-By-Height

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

Random Union

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

Сжатие путей

Используется чтобы ускорить операцию Find(). При каждом новом поиске, все элементы находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция 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
    a[x]:=find(a[x]);
  find:=a[x];
end;
 
procedure union(x,y:integer);
begin
  x:=find(x);
  y:=find(y);
  if x<>y then
    if random <= 0.5 then
      a[x]:=y
    else
      a[y]:=x;
end;
 
begin
  randomize;
end.

См. также

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

Литература

• Томас Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.

Ссылки

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