На этом шаге рассмотрим работу алгоритма Крускала.

    Алгоритм Крускала работает следующим образом:

for i:=1 to N do Makeset(i);

    Вначале строятся N (по числу вершин) непересекающихся множеств, каждое из которых хранит номера вершин, в него входящих (вначале каждое такое множество хранит только одну вершину — с номером вершины, соответствующим номеру множества).

    Далее осуществляется цикл по всем ребрам (B[i], E[i]) с весом R[i] (в порядке возрастания весов R[i]). Если ребро (B[i], E[i]) соединяет два разных множества FindSet(B[i]) x FindSet(E[i]), то это ребро включается в минимальный остовный граф, его вес добавляется к ответу: Answer := Answer + R[i], а сами множества объединяются (как связывающиеся данным ребром): Union(B[i],E[i]);

    Рассмотрим подробнее процедуры, которые реализуют работу с множеством непересекающихся подмножеств вершин в процессе построения минимального остовного дерева. Все они работают с двумя массивами: Pred[1 ..N] и Rank[1 ..N]. Массив Pred[i] содержит номер вершины — предка. Массив Rank[i] содержит ранг вершины. Понятие ранга вводится для ускорения обработки.

    Процедура MakeSet осуществляет начальное построение системы независимых множеств вершин:

procedure MakeSet(х:longint); 
begin 
  Pred[x]:=x;  {вначале вершина ссылается сама на себя} 
  rank[x]:=0; {ранг ее равен 0} 
end;  

    Рекурсивная функция FindSet(x) отвечает на вопрос: "Какому множеству из построенной системы подмножеств принадлежит вершина?" Каждое из подмножеств фактически представляет собой поддерево, и функция FindSet возвращает номер вершины, которая является корнем этого поддерева.

function FindSet(х:longint):longint; 
begin 
  if x <> Pred[x] then 
    Pred[x]:=FindSet(Pred[x]);
  FindSet:=Pred[x];
end;

    Процедура Union(x, у) вызывается в том случае, если вершины х и у лежат в разных поддеревьях, и служит для объединения этих поддеревьев. При этом она находит корни соответствующих поддеревьев, вызывая рекурсивную функцию FindSet два раза Findset(x) и FindSet(y), а затем вызывает процедуру Link для объединения деревьев с заданными корнями:

procedure Union(x, y:longint); 
begin 
  Link (FindSet(x),FindSet(y)); 
end; 

    Процедура Link(x, у) осуществляет объединение деревьев с корнями х и у и перестроение рангов вершин, входящих в эти деревья.

procedure Link(x,y:longint); 
begin 
  if rank[x] > rank[y] then 
    pred[y]:=x
  else 
  begin 
    pred[x]:=y; 
    if rank[x]=rank[y] then 
      inc(rank[y]);
  end; 
end;

    Напомним, что ранги вершин обеспечивают сокращение количества операций (и соответственно времени), затрачиваемых на обработку системы непересекающихся поддеревьев.

    На следующем шаге рассмотрим быструю сортировку.

Предыдущий шаг Содержание Следующий шаг