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

Система непересекающихся множеств (англ. disjoint-set, или union–find data structure) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: ${\displaystyle \{\mathrm {Union} ,\mathrm {Find} ,\mathrm {MakeSet} \}}$.

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

Определение[править | править код]

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

${\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}$.

Каждому подмножеству ${\displaystyle X_{i}}$ назначается представитель ${\displaystyle r_{i}\in X_{i}}$. Соответствующая система непересекающихся множеств поддерживает следующие операции:

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

Алгоритмическая реализация[править | править код]

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

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

Эвристики[править | править код]

Для ускорения операций Union и Find могут быть использованы эвристики Union-By-Size, Union-By-Height, Random-Union и сжатие путей.

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

Эвристика Union-By-Height аналогична Union-By-Size, но использует высоту дерева вместо размера.

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

Эвристика сжатия путей используется, чтобы ускорить операцию ${\displaystyle \mathrm {Find} (x)}$. При каждом новом поиске все элементы, находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция Find будет работать в среднем ${\displaystyle \alpha (n)}$, где ${\displaystyle \alpha }$ — функция, обратная функции Аккермана. Это позволяет значительно ускорить работу, так как ${\displaystyle \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. (англ.)
• Tarjan, Robert E., and Jan Van Leeuwen. «Worst-case analysis of set union algorithms.» // Journal of the ACM 31.2 (1984): 245—281. (англ.)
• Томас Кормен и др. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.

Ссылки[править | править код]

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

Для улучшения этой статьи желательно: Проставить сноски, внести более точные указания на источники. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.