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

Дано. Связный неориентированный граф G=< V, E>. Ребра имеют вес. Граф описывается матрицей смежности А (Array [1..N, 1..N] Of Integer). Элемент матрицы, не равный нулю, определяет вес ребра.

Результат. Каркас с минимальным суммарным весом Q=(V, T), где T E.

Отличие от метода Краскала заключается в том, что на каждом шаге строится дерево, а не ациклический граф, т. е. добав­ляется ребро с минимальным весом, одна вершина которого принадлежит каркасу, а другая нет. Такой принцип «добавле­ния» исключает возможность появления циклов. Для реализа­ции метода необходимы две величины множественного типа SM и SP (Set Of 1..N). Первона­чально значением SM являют­ся все вершины графа, a SP пу­сто. Если ребро < i, j> включается в 7\ то один из но­меров вершин i и / исключает­ся из SM и добавляется в SP (кроме первого шага, на кото­ром оба номера переносятся в SP).

 

 

рис.2

Пример. На рисунке 2 приведен граф, для которого последовательно строится каркас. Процесс построения (изменения SM, SP) показан на следующих рисунках.

 

		SM-[1, 2, 5..7] SP-[3, 4]
			SM-[1, 5..7] SP-[2.-4]

 

 

рис.3

Логика построения каркаса.

Procedure Tree; { *А - глобальная структура данных. *}

Var SM, SP: Set Of 1..N;

min, i, j, 1, k, t: Integer;

Begin

min: =maxint; SM: =[1..N];

SP: =[];

{*Включаем первоеребро в каркас. *}

For i: =l То N-l Do

For j: =i+l To N Do

If (A[i, j]< min) And (A[i, j]< > 0) Then

Begin

min: =A[i, j]; 1: =i; t: =j;

End;

SP: = [l, t]; SM: =SM-[l, t] < выводим илизапоминаем ребро < l, t»;

{^Основной цикл. *} While SM< > [] Do Begin min: =maxint; l: =0; t: =0; For i: =l To N Do If Not (i In SP) Then For j: =1 To N Do If (j In SP) And (A[i, j]< min) And (A[i, j]< > 0) Then

Begin min: =A[j, k]; 1: =i; t: =j; End; SP: =SP+[1]; SM: =SM-[1]; < выводим или запоминаем ребро < lft»;

End;

End;