Каркас минимального веса. Метод Дж. Краскала

Дано. Связный неориентированный граф G=< V, E>. Ребра имеют вес. Граф описывается перечнем ребер с указанием их веса. Массив Р (Array[1..3, 1..N*(N-1) Div 2] Of Integer). Резу­льтат. Каркас с минимальным суммарным весом Q=< V, T>, где T< zE.

Пример. Граф и процесс построения каркаса по методу Крас-кала.

Шаг 1. Начать с графа Q, содержащего N вершин и не имею­щего ребер.

Шаг 2. Упорядочить ребра графа G в порядке неубывания их

весов.

Шаг 3. На­чав с первого ребра в этом перечне, до­бавлять ребра в граф Q, со­блюдая усло­вие: добавле­ние не должно приводить к появлению цикла в Q.

 

 

 

 

рис.1

Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в Q не станет равным N-1. Получившееся дерево является каркасом минимального веса.

Какие структуры данных требуются для реализации шага 3? Стандартным в программировании методом является введение массива меток вершин графа (Мark: Array[ 1..N] Of Integer). Начальные значения элементов массива равны номерам соот­ветствующих вершин (Mark[i]=i для i от 1 до N). Ребро выби­рается в каркас в том случае, если вершины, соединяемые им, имеют разные значения меток. В этом случае циклы не образу­ются. Для примера, приведенного выше, процесс изменения Mark показан в таблице 1.

Таблица 1

Номер итерации	Ребро	Значения элементов Маrк
Начальное значение	-	[1, 2, 3, 4, 5]
	< 1, 4>	[1, 2, 3, 1, 5]
	< 4, 5>	[1, 2, 3, 1, 1]
	< 2, 3>	[1, 2, 2, 1, 1]
	< 2, 5>	[1, 1, 1.1, 1]

 

И логика этого фрагмента.

Procedure Chang_Mark (1, т: Integer);

{*Массив Mark глобальный.*}

Var ift: Integer;

Begin

If m< l Then

Begin t: =l; l: =m; m: =t

End;

For i: =l To N Do If Mark[i]=m

Then Mark[i]: =1;

End;

Фрагмент основной части логики.

Program Tree;

Const N=..;

Var P: Array[1.. 3, 1..N* (N-1) Div 2] Of Integer; Mark: Array[1..N] Of Integer; k, i, t: Integer;

M: Integer; {*Количество ребер графа.*}

Begin

< ввод описания графа - массив Р>;

< сортировка массива Р по значениям весов ребер>;

For i: =l То N Do

Mark[i]: =i; k: =0; t: =M;

While k< N-l Do

Begin i: =l;

While (i< =t) And (Mark[P[1, i]] =Mark[P[2, i]])And < P[l, i]< > 0) Do

Inc(i); Inc (k);

< Запоминание ребра каркаса>; Change_Mark(Mark[P[l, i]], Mark[P[2, i}]); End;

End;