Система непересекающихся множеств (англ. disjoint-set, или union–find data structure) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: .
Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.
Пусть конечное множество, разбитое на непересекающиеся подмножества (классы) :
Каждому подмножеству назначается представитель . Соответствующая система непересекающихся множеств поддерживает следующие операции:
Тривиальная реализация сохраняет принадлежность элементов из и представителей в индексном массиве. На практике же чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Find. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.
Для ускорения операций Union и Find могут быть использованы эвристики Union-By-Size, Union-By-Height, Random-Union и сжатие путей.
В эвристике Union-By-Size во время операции корень меньшего дерева вешается под корень большего дерева. Благодаря этому подходу сохраняется балансировка дерева. Глубина каждого поддерева не может превысить величину . При использовании этой эвристики время операции Find в худшем случае уменьшается с до . Для эффективной реализации предлагается сохранять в корне количество узлов в дереве.
Эвристика Union-By-Height аналогична Union-By-Size, но использует высоту дерева вместо размера.
В эвристике Random-Union используется тот факт, что можно не тратить дополнительные памяти на сохранение количества узлов в дереве: достаточно выбирать корень случайным образом — такое решение даёт на случайных запросах скорость, вполне сравнимую с другими реализациями. Тем не менее, если имеется много запросов вида «объединить большое множество с маленьким», данная эвристика улучшает матожидание (то есть среднее время работы) всего в два раза, поэтому использовать её без эвристики сжатия путей не рекомендуется.
Эвристика сжатия путей используется, чтобы ускорить операцию . При каждом новом поиске все элементы, находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция Find будет работать в среднем , где — функция, обратная функции Аккермана. Это позволяет значительно ускорить работу, так как для всех применяемых на практике значений принимает значение, меньшее 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:
1 const MAX_N = 1000;
2
3 var Parent , Rank : array [ 1 .. MAX_N ] of LongInt;
4
5 procedure swap ( var x , y : LongInt );
6 var tmp : LongInt;
7 begin
8 tmp := x;
9 x := y;
10 y := tmp;
11 end;
12
13 procedure MakeSet ( x : LongInt ) ;
14 begin
15 Parent[x] := x;
16 Rank[x] := 0;
17 end;
18
19 function Find ( x : LongInt ) : LongInt;
20 begin
21 if ( Parent[x] <> x ) then
22 Parent[x] := Find ( Parent[x] );
23 Exit ( Parent[x] );
24 end;
25
26 procedure Union ( x , y : LongInt );
27 begin
28 x := Find ( x );
29 y := Find ( y );
30 if ( x = y ) then exit();
31 if ( Rank[x] < Rank[y] ) then swap ( x , y );
32
33 Parent[y] := x;
34 if ( Rank[x] = Rank[y] ) then
35 inc ( Rank[x] );
36 end;
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .