Листинг 5.2.2. Программа выполнения алгоритма Прима
procedure Prim ( С: аггау[1..n, 1..n] of real );
{ Prim печатает ребра остовного дерева минимальной стоимости
для графа с вершинами {1, ..., n} и матрицей стоимости С}
var
LOWCOST: array[1..n] of real;
CLOSEST: array[1..n] of integer;
i, j, k, min: integer;
{ i и j — индексы. При просмотре массива LOWCOST
к — номер найденной вершины, min = LOWCOST[k] }
begin
(1) for i:= 2 to n do begin
{ первоначально в множестве U только вершина 1 }
(2) LOWCOST[i]:= СП, i];
(3) CLOSEST[i]:= 1
end;
(4) for i:= 2 to n do begin { поиск вне множества U наилучшей вершины к, имеющей
инцидентное ребро, оканчивающееся в множестве U }
(5) min:= LOWCOST[2];
(6) k:= 2;
(7) for j:= 3 to n do
(8) if LOWCOST[j] < min then begin
(9) min:= LOWCOST[j];
(10) k:= j
end;
(11) writeln{k, CLOSEST[k]); { вывод ребра на печать }
(12) LOWCOST[k] := infinity; { к добавляется в множество U }
(13) for j:= 2 to n do { корректировка стоимостей в U }
(14) if (C[k, j] < LOWCOST[j]) and
(LOWCOST[j] < infinity) then begin
(15) LOWCOST[j]:= C[k, j];
(16) CLOSEST[j]:= k
end
end
end; { Prim }
Пример. Рассмотрим этапы построения остовного дерева минимальной стоимости для графа на рис. 5.2.1.
Рис. 5.2.1.
Решение.Результаты последовательных итераций приведем в таблице
Множество U
Ребро {u, v}
Стоимость
с{u,v}
Вершина v
{1}
{1,3}
{1,3}
{3,6}
{1,3,6}
{6,4}
{1,3,6,4}
{3,2}
{1,3,6,4,2}
{2,5}
{1,3,6,4,2,5} = V
Этапы построения остовного дерева минимальной стоимости изображены на рис. 5.2.2.
Рис.5.2.2
Время выполнения алгоритма Прима имеет порядок , поскольку выполняется итерация внешнего цикла строк (4) – (16), а каждая итерация этого цикла требует времени порядка для выполнения внутренних циклов в строках (7)-(10) и (13)–(16). Если значение достаточно большое, то использование этого алгоритма нерационально.
Далее мы рассмотрим алгоритм Краскала нахождения остовного дерева минимальной стоимости, который выполняется за время порядка , где — количество ребер в данном графе. Если значительно меньше , то алгоритм Краскала предпочтительнее, но если близко к , рекомендуется применять алгоритм Прима.
Снова предположим, что дан связный граф с множеством вершин и функцией стоимости , определенной на множестве ребер . В процессе построения остовного дерева минимальной стоимости с помощью алгоритма Краскала (Kruskal) имеется набор связных компонент графа, постепенно объединяя которые формируется остовное дерево.
1. Построение остовного дерева минимальной стоимости для графа начинается с графа , состоящего только из n вершин графа и не имеющего ребер. Таким образом, каждая вершина является связной (с самой собой) компонентой.
2. Поочередно проверяются ребра из множества Е в порядке возрастания их стоимости. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в граф Т, объединяя две компоненты.
Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связную компоненту, являющуюся свободным деревом, по теореме 1(2), приведет к образованию цикла.
3. Когда все вершины графа G будут принадлежать одной компоненте, построение остовного дерева минимальной стоимости Т для этого графа заканчивается.
Пример. Рассмотрим помеченный граф, представленный на рис. 5.2.1.
Последовательность рассмотрения и добавления ребер в формирующееся дерево Т показана в таблице.
Ребра {u, v} по возрастанию стоимости
Стоимость с{u,v}
{1,3}
принимается
{4,6}
принимается
{2,5}
принимается
{3,6}
принимается
{3,4}
отвергается, образует цикл с {3, 6} и {4, 6}
{2,3}
принимается
На рис. 5.3.1 графически представлены этапы построения остовного дерева минимальной стоимости.
Рис 5.3.1.
Этот алгоритм можно реализовать, основываясь на множествах (для вершин и ребер) и операторах. Прежде всего, необходимо множество ребер Е, к которому можно было бы последовательно применять оператор удаления ребра наименьшей стоимости DELETEMIN для отбора ребер в порядке возрастания их стоимости. Поэтому множество ребер целесообразно представить в виде очереди с приоритетами и использовать для нее частично упорядоченное дерево в качестве структуры данных.
Необходимо также поддерживать набор С связных компонент, для чего можно использовать следующие операторы.
1. Оператор MERGE(A, В, С) объединяет компоненты А и В из набора С и результат объединения помещает или в А, или в В.
2. Функция FIND(v, С) возвращает имя той компоненты из набора С, которая содержит вершину v.
3. Оператор INITIAL(A, v, С) создает в наборе С новую компоненту с именем А, содержащую только одну вершину v.
