АЛГОРИТМЫ ДЛЯ НАХОЖДЕНИЯ ОБЪЕДИНЕНИЙ

З а д а ч а: даны элементы 1,2, ..., n. Вначале каждый

элемент образует одноэлементное множество. Нужно выполнить

последовательность операций ОБЪЕДИНИТЬ и НАЙТИ. Будем предпо-

лагать, что множества именуются числами от 1 до n. В частнос-

ти, вначале i = { i } (i=1,...n).

1. АЛГОРИТМЫ С ИСПОЛЬЗОВАНИЕМ МАССИВОВ И СПИСКОВ

     Для представления множеств используем 6 массивов размера

1 х n   с элементами-числами из [1,n].

  R[i] - внутреннее имя множества, в которое входит i;

  СЛЕД[i] - следующий элемент множества, в которое входит i,

если i - последний элемент, то СЛЕД[i] = 0;

  СПИСОК[j] - первый элемент множества с внутренним именем j;

  РАЗМЕР[j] - количество элементов множества с внутр. именем j;

  ВНУТР_ИМЯ[k] - внутреннее имя множества с внешним именем k;

  ВНЕШ_ИМЯ[j] - внешнее имя множества с внутренним именем j.

function НАЙТИ(i);

НАЙТИ := ВНЕШ_ИМЯ[R[i]]

   end.

procedure ОБЪЕДИНИТЬ(A,B,C):

begin

1.  if  РАЗМЕР[ВНУТР_ИМЯ[A]] <= РАЗМЕР[ВНУТР_ИМЯ[B]]

then begin I := ВНУТР_ИМЯ[A]; J:=ВНУТР_ИМЯ[B] end

      else begin I := ВНУТР_ИМЯ[B]; J:=ВНУТР_ИМЯ[A] end;

/* I -  имя меньшего мн-ва, J - большего мн-ва */

2.  E := СПИСОК[I];

3.  while E <>0 do  /* переименование меньшего мн-ва

begin  R[E] := J; LAST := E; E := СЛЕД[E]  end;

/* слияние множеств:

4.  СЛЕД[LAST] := СПИСОК[J]; СПИСОК[J] := СПИСОК[I];

    РАЗМЕР[J] := РАЗМЕР[J] +  РАЗМЕР[I];

    /* изменение внешнего имени

5.  ВНУТР_ИМЯ[C] := J; ВНЕШ_ИМЯ[J] := C

   end.

ТЕОРЕМА 1. С помощью приведенных выше алгоритмов последовательность из m операций НАЙТИ и n-1 операций ОБЪЕДИНИТЬ можно выполнить за время

O(MAX(m, nlog(n))).

-------------------------------------------------------------

     2. АЛГОРИТМЫ С ИСПОЛЬЗОВАНИЕМ ДЕРЕВЬЕВ (со сжатием путей)

     Структуры данных - 4 массива размера 1хn :

     ОТЕЦ[i] - отец вершины i в дереве; если i - корень, то 0;

     ИМЯ[i] - имя множества элементов в вершинах дерева с

корнем i;

     РАЗМЕР[i] - количество элементов во множестве с корнем i;

     КОРЕНЬ[j] - корень дерева, элементы которого образуют

множество с именем j.

     Инициализация: ОТЕЦ[i]=0, ИМЯ[i]=i, СЧЕТ[i]=1,

КОРЕНЬ[i]=i  для всех i из [1,n].

function НАЙТИ(i):

     begin

     СПИСОК := пустой_список;

v:=i;

     while ОТЕЦ[v] <>0 do

begin добавить v в СПИСОК;

             v := ОТЕЦ[v]

       end;    /* v - корень

     НАЙТИ ;= ИМЯ[v];

     /* изменение отцов вершин из СПИСКА на v:

for all w из СПИСОК do ОТЕЦ[w] := v

     end

procedure ОБЪЕДИНИТЬ(A,B,C):

begin

   .  if  РАЗМЕР[КОРЕНЬ[A]] <= РАЗМЕР[КОРЕНЬ[B]]

then begin I := КОРЕНЬ[A]; J :=КОРЕНЬ[B]  end

        else begin I := КОРЕНЬ[B]; J :=КОРЕНЬ[A]  end;

/* I - корень меньшего дерева, J - большего

      ОТЕЦ[I] := J;

      РАЗМЕР[J] := РАЗМЕР[J] +  РАЗМЕР[I];

      ИМЯ[J] := C;  КОРЕНЬ[C] := J

end

  ------------------------------------------

Пусть F(0)=1, F(i+1) = 2^F(i). Определим G(n) = min{ k |

F(k) >=n}. G - медленно растущая функция (покажите, что для

любого k и всех больших n G(n)<log(k,n)=loglog...(k раз)logn).

ТЕОРЕМА 2. Пусть с - некоторая константа. Тогда найдется

такая константа с' (зависяшая от с), что алгоритмы со сжатием

путей позволяют выполнять любую последовательность из cn опе-

раций ОБЪЕДИНИТЬ и НАЙТИ  не более чем за c'nG(n) шагов.

-----------------------------------------------------------

З а д а ч и.

     1. Пусть операция РАСПЕЧАТАТЬ(А) по имени множества вы-

водит на печать список его элементов. Реализуйте эту операцию

для (а) спискового представления множеств и (б) представления

с помощью деревьев. Оцените сложность получившихся процедур.

Как изменить структуры данныхв случае (б), чтобы время распе-

чатки множества зависело только от его размера?

     2. Пусть в последовательности операций сначала идут n1

операций ОБЪЕДИНИТЬ, а затем n2 операций НАЙТИ. Доказать, что

алгоритм со сжатием путей выполняет такую последовательность

за время O(n1+n2).