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

Система непересекающихся множеств (Шаблон:Lang-en, или Шаблон:Lang-en2 Шаблон:Lang-en2) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: $\{\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{o}\mathrm{n},\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{d},\mathrm{M}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{t}\}$.

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

Определение

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

$S=X_0\cup X_1\cup X_2\cup \dots \cup X_k:X_i\cap X_j=\varnothing \mathrm{\forall }i,j\in \{0,1,\dots ,k\},i\ne j$.

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

• $\mathrm{M}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{t}(x)$: создаёт для элемента $x$ новое подмножество. Назначает этот же элемент представителем созданного подмножества.
• $\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{o}\mathrm{n}(r,s)$: объединяет оба подмножества, принадлежащие представителям $r$ и $s$, и назначает $r$ представителем нового подмножества.
• $\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{d}(x)$: определяет для $x\in S$ подмножество, к которому принадлежит элемент, и возвращает его представителя.

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

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

• $\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{o}\mathrm{n}(r,s)$: вешает корень более низкого дерева под корень более высокого дерева. Если при этом $r$ становится потомком $s$, оба узла меняются местами.
• $\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{d}(x)$: проходит путь от $x$ до корня дерева и возвращает его (корень в данном случае является представителем).

Эвристики

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

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

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

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

Эвристика сжатия путей используется, чтобы ускорить операцию $\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{d}(x)$. При каждом новом поиске все элементы, находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция Шаблон:Math будет работать в среднем $\alpha (n)$, где $\alpha$ — функция, обратная функции Аккермана. Это позволяет значительно ускорить работу, так как $\alpha$ для всех применяемых на практике значений принимает значение, меньшее 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:

const MAX_N = 1000;

var Parent , Rank : array [ 1 .. MAX_N ] of LongInt;

procedure swap ( var x , y : LongInt );
  var tmp : LongInt;
begin
  tmp := x; 
  x := y; 
  y := tmp;
end;

procedure MakeSet ( x : LongInt ) ;
begin
  Parent[x] := x;
  Rank[x] := 0;
end;

function Find ( x : LongInt ) : LongInt;
begin
  if ( Parent[x] <> x ) then
    Parent[x] := Find ( Parent[x] );
  Exit ( Parent[x] );
end;

procedure Union ( x , y : LongInt );
begin
  x := Find ( x );
  y := Find ( y );
  if ( x = y ) then exit();
  if ( Rank[x] < Rank[y] ) then swap ( x , y );
  
  Parent[y] := x;
  if ( Rank[x] = Rank[y] ) then
    inc ( Rank[x] );
end;

См. также

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

Литература

• Galler, Bernard A., and Michael J. Fisher. «An improved equivalence algorithm.» // Communications of the ACM, 7.5 (1964): 301—303.Шаблон:Ref-en
• Tarjan, Robert E., and Jan Van Leeuwen. «Worst-case analysis of set union algorithms.» // Journal of the ACM 31.2 (1984): 245—281.Шаблон:Ref-en
• Шаблон:Книга

Ссылки

• Union-Find / Kevin Wayne, Pearson-Addison WesleyШаблон:Ref-en
• Chapter 22: Data Structures For Disjoint Sets / Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. RivestШаблон:Ref-en
• Визуализатор работы некоторых структур данных для непересекающихся множеств / ИТМО
• Реализация непересекающихся множеств в коллекции библиотек C++ Boost, 2006