|
|
| (не показаны 2 промежуточные версии этого же участника) |
| Строка 1: |
Строка 1: |
| '''Система непересекающихся множеств''' ({{lang-en|disjoint-set}}, или {{lang-en2|union–find}} {{lang-en2|data structure}}) — [[структура данных]], которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: <math>\{\mathrm{Union}, \mathrm{Find}, \mathrm{MakeSet}\}</math>. | | '''Система непересекающихся множеств''' — [[структура данных]], которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: <math>\{\mathrm{Union}, \mathrm{Find}, \mathrm{MakeSet}\}</math>. |
|
| |
|
| Применяется для хранения [[Компонента связности графа|компонент связности]] в [[Граф (математика)|графах]], в частности, [[Алгоритм Краскала|алгоритму Краскала]] необходима подобная структура данных для эффективной реализации. | | Применяется для хранения [[Компонента связности графа|компонент связности]] в [[Граф (математика)|графах]], в частности, [[Алгоритм Краскала|алгоритму Краскала]] необходима подобная структура данных для эффективной реализации. |
| Строка 20: |
Строка 20: |
| * <math>\mathrm{Find}(x)</math>: проходит путь от <math>x</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}}
| |
| [[Категория:Структуры данных]] | | [[Категория:Структуры данных]] |
Система непересекающихся множеств — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: [math]\displaystyle{ \{\mathrm{Union}, \mathrm{Find}, \mathrm{MakeSet}\} }[/math].
Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.
Определение
Пусть [math]\displaystyle{ S }[/math] конечное множество, разбитое на непересекающиеся подмножества (классы) [math]\displaystyle{ X_i }[/math]:
- [math]\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 }[/math].
Каждому подмножеству [math]\displaystyle{ X_i }[/math] назначается представитель [math]\displaystyle{ r_i \in X_i }[/math].
Соответствующая система непересекающихся множеств поддерживает следующие операции:
- [math]\displaystyle{ \mathrm{MakeSet}(x) }[/math]: создаёт для элемента [math]\displaystyle{ x }[/math] новое подмножество. Назначает этот же элемент представителем созданного подмножества.
- [math]\displaystyle{ \mathrm{Union}(r, s) }[/math]: объединяет оба подмножества, принадлежащие представителям [math]\displaystyle{ r }[/math] и [math]\displaystyle{ s }[/math], и назначает [math]\displaystyle{ r }[/math] представителем нового подмножества.
- [math]\displaystyle{ \mathrm{Find}(x) }[/math]: определяет для [math]\displaystyle{ x \in S }[/math] подмножество, к которому принадлежит элемент, и возвращает его представителя.
Алгоритмическая реализация
Тривиальная реализация сохраняет принадлежность элементов из [math]\displaystyle{ S }[/math] и представителей [math]\displaystyle{ r_i }[/math] в индексном массиве. На практике же чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Шаблон:Math. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.
- [math]\displaystyle{ \mathrm{Union}(r, s) }[/math]: вешает корень более низкого дерева под корень более высокого дерева. Если при этом [math]\displaystyle{ r }[/math] становится потомком [math]\displaystyle{ s }[/math], оба узла меняются местами.
- [math]\displaystyle{ \mathrm{Find}(x) }[/math]: проходит путь от [math]\displaystyle{ x }[/math] до корня дерева и возвращает его (корень в данном случае является представителем).
