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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Система непересекающихся множеств (англ. 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:

procedure makeset(x:integer);
begin
  a[x]:=x;
end;

function find(x:integer):integer;
begin
  if a[x]<>x then
    a[x]:=find(a[x]);
  find:=a[x];
end;

procedure union(x,y:integer);
begin
  x:=find(x);
  y:=find(y);
  if x<>y then
    if random <= 0.5 then
      a[x]:=y
    else
      a[y]:=x;
end;

begin
  randomize;
end.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]