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

2020-12-22T19:08:24Z

31.186.66.108: /* Определение */

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

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

== Определение ==
Пусть <math>S</math> конечное множество, разбитое на непересекающиеся подмножества ([[Класс (математика)|классы]]) <math>X_i</math>:

: <math>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>X_i</math> назначается представитель <math>r_i \in X_i</math>.
Соответствующая система непересекающихся множеств поддерживает следующие операции:
* <math>\mathrm{MakeSet}(x)</math>: создаёт для элемента <math>x</math> новое подмножество. Назначает этот же элемент представителем созданного подмножества.
* <math>\mathrm{Union}(r, s)</math>: объединяет оба подмножества, принадлежащие представителям <math>r</math> и <math>s</math>, и назначает <math>r</math> представителем нового подмножества.
* <math>\mathrm{Find}(x)</math>: определяет для <math>x \in S</math> подмножество, к которому принадлежит элемент, и возвращает его представителя.

== Алгоритмическая реализация ==
Тривиальная реализация сохраняет принадлежность элементов из <math>S</math> и представителей <math>r_i</math> в [[Индексный массив|индексном массиве]]. На практике же чаще используются множества [[Дерево (теория графов)|деревьев]]. Это позволяет существенно сократить время, необходимое для операции {{math|Find}}. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.

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

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

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

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

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

Эвристика сжатия путей используется, чтобы ускорить операцию <math>\mathrm{Find}(x)</math>. При каждом новом поиске все элементы, находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция {{math|Find}} будет работать в среднем <math>\alpha(n)</math>, где <math>\alpha</math> — функция, обратная [[Функция Аккермана|функции Аккермана]]. Это позволяет значительно ускорить работу, так как <math>\alpha</math> для всех применяемых на практике значений принимает значение, меньшее 5.

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

Реализация на C++:
<source lang="cpp">
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];
}
}
</source>

Реализация на Free Pascal:
<source lang="pascal" line="1">
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;

</source>

== См. также ==
* [[Лес непересекающихся множеств]]

== Литература ==
* [https://www.enseignement.polytechnique.fr/informatique/ARCHIVES/IF/03/pi/levy2/fischer-galler.pdf Galler, Bernard A., and Michael J. Fisher. «An improved equivalence algorithm.»] // [[Communications of the ACM]], 7.5 (1964): 301—303.{{ref-en}}
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.435.9355&rep=rep1&type=pdf 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}}
* {{книга
|автор = Томас Кормен и др.
|заглавие = Алгоритмы: построение и анализ
|оригинал = Introduction to Algorithms
|ссылка =
|издание = 2-е изд
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страницы = 1296
|isbn = 0-07-013151-1
}}

== Ссылки ==
* [https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf Union-Find] / Kevin Wayne, Pearson-Addison Wesley{{ref-en}}
* [http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap22.htm Chapter 22: Data Structures For Disjoint Sets] / Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest{{ref-en}}
* [https://web.archive.org/web/20140924062309/http://rain.ifmo.ru/cat/view.php/vis/unsorted/disjoint-sets-2003 Визуализатор работы некоторых структур данных для непересекающихся множеств] / ИТМО
* [http://www.boost.org/doc/libs/1_35_0/libs/disjoint_sets/disjoint_sets.html Реализация непересекающихся множеств в коллекции библиотек C++ Boost], 2006

{{Структуры данных}}

{{rq|refless}}
[[Категория:Структуры данных]]

Поле цифровой дидактики - Вклад [ru]

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