5.3. Алгоритм Краскала.

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

1. Построение остовного дерева минимальной стоимости для графа начинается с графа , состоящего только из n вершин графа и не имеющего ребер. Таким образом, каждая вершина является связной (с самой собой) компонентой.

2. Поочередно проверяются ребра из множества Е в порядке возрастания их стоимости. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в граф Т, объединяя две компоненты.

Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связную компоненту, являющуюся свободным деревом, по теореме 1(2), приведет к образованию цикла.

3. Когда все вершины графа G будут принадлежать одной компоненте, построение остовного дерева минимальной стоимости Т для этого графа заканчивается.

Пример. Рассмотрим помеченный граф, представленный на рис. 5.2.1.

Последовательность рассмотрения и добавления ребер в формирующееся дерево Т показана в таблице.

Ребра {u, v} по возрастанию стоимости	Стоимость с{u,v}
{1,3}	1	принимается
{4,6}	2	принимается
{2,5}	3	принимается
{3,6}	4	принимается
{3,4}	5	отвергается, образует цикл с {3, 6} и {4, 6}
{2,3}	5	принимается

На рис. 5.3.1 графически представлены этапы построения остовного дерева минимальной стоимости.

Рис 5.3.1.

Этот алгоритм можно реализовать, основываясь на множествах (для вершин и ребер) и операторах. Прежде всего, необходимо множество ребер Е, к которому можно было бы последовательно применять оператор удаления ребра наименьшей стоимости DELETEMIN для отбора ребер в порядке возрастания их стоимости. Поэтому множество ребер целесообразно представить в виде очереди с приоритетами и использовать для нее частично упорядоченное дерево в качестве структуры данных.

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

1. Оператор MERGE(A, В, С) объединяет компоненты А и В из набора С и результат объединения помещает или в А, или в В.

2. Функция FIND(v, С) возвращает имя той компоненты из набора С, которая содержит вершину v.

3. Оператор INITIAL(A, v, С) создает в наборе С новую компоненту с именем А, содержащую только одну вершину v.

Листинг 5.3.1. Программа, реализующая алгоритм Краскала

procedure Kruskal ( V: SET; Е: SET; var T: SET );

{ V — множество вершин, Е и Т — множества дуг }

var

ncomp: integer; { текущее количество компонент }

edges: PRIORITYQUEUE;

{множество дуг, реализованное как очередь с приоритетами}

components: MFSET;

{ множество V, сгруппированное в множество компонент }

u, v: вершина;

е: ребро;

nextcomp: integer; { имя (номер) новой компоненты }

ucomp, vcomp: integer; { имена (номера) компонент }

begin

MAKENULL(Т) ;

MAKENULL(edges) ;

Nextcomp:= 0;

ncomp:= число элементов множества V;

for v V do begin { инициализация компонент,

содержащих по одной вершине из V }

nextcomp:= nextcomp + 1;

INITIAL(nextcomp, v, components)

end;

for e E do { инициализация очереди с приоритетами,

содержащей ребра }

INSERT(e, edges);

while ncomp > 1 do begin { рассматривается следующее ребро }

е:= DELETEMIN(edges) ;

пусть е = (u, v);

ucomp:= FIND(u, components);

vcomp:= FIND(v, components);

if ucorap <> vcomp then begin

{ ребро е соединяет две различные компоненты }

MERGE(ucomp, vcorap, components);

ncomp:= ncomp - 1;

INSERT(e, T)

end

end

end; { Kruskal }

Время выполнения этой программы зависит от двух факторов. Если в исходном графе G всего е ребер, то для вставки их в очередь с приоритетами потребуется время порядка . Каждая итерация цикла while для нахождения ребра с наименьшей стоимостью в очереди edges требует времени порядка . Поэтому выполнение всего этого цикла в самом худшем случае потребует времени . Вторым фактором, влияющим на время выполнения программы, является общее время выполнения операторов MERGE и FIND. В любом случае алгоритм Краскала может быть выполнен за время .

76