Русская Википедия:Система непересекающихся множеств

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Система непересекающихся множеств (Шаблон:Lang-en, или Шаблон:Lang-en2 Шаблон:Lang-en2) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: <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. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.

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

Эвристики

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

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

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

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

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

См. также

Литература

Ссылки

Шаблон:Структуры данных

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Система_непересекающихся_множеств&oldid=10802578