Листинг 5.2.1. Эскиз алгоритма Прима

Алгоритм Прима.

Пусть дан граф , . Множество вершин , входящих в остовное дерево минимальной стоимости, строится в алгоритме Прима (Prim) по следующим правилам:

1. Сначала состоит из одной произвольной вершины. Например, .

2. На каждом шаге алгоритма находится ребро наименьшей стоимости такое, что и . Ребро добавляется к дереву, вершина переносится из множества во множество .

Согласно теореме 2, существует остовное дерево минимальной стоимости графа , содержащее новое множество вместе с ребром .

3. Шаг 2 повторяется до тех пор, пока множество не станет равным множеству , то есть, пока не будет достигнуто . Это означает, что в остовное дерево будут включены все вершины графа и некоторые его ребра. По теореме 2, существует остовное дерево минимальной стоимости графа , содержащее именно те ребра, которые выбирались на шаге 2. Значит, полученное остовное дерево и является остовным деревом минимальной стоимости.

Эскиз алгоритма показан в листинге 5.2.1.

procedure Prim ( G: граф; var T: множество ребер );

var

U: множество вершин;

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

begin

T:= ;

U:= {1};

while U V do begin

нахождение ребра (u, v) наименьшей стоимости и такого,

что и ;

Т:= Т ;

U:= U

end

end; { Prim }

Для выбора ребра с наименьшей стоимостью, соединяющего множества и на каждом шаге алгоритма используются два массива. Массив CLOSEST[i] для каждой вершины i из множества содержит вершину из , с которой она соединена ребром минимальной стоимости (это ребро выбирается среди ребер, инцидентных вершине i, и которые ведут в множество ). Другой массив LOWCOST[i] хранит значение стоимости ребра (i, CLOSEST[i]).

На каждом шаге алгоритма просматривается массив LOWCOST, находится минимальное значение LOWCOST[k] (строки (5)-(10)). Вершина k принадлежит множеству и соединена ребром с вершиной из множества . Затем выводится на печать ребро (k, CLOSEST[k]) (строка (11)).

После нахождения очередной вершины k остовного дерева значение LOWCOST[k] устанавливается равным infinity (бесконечность), очень большому числу, такому, чтобы эта вершина уже в дальнейшем не рассматривалась (строка (12)). Значение числа infinity должно быть больше стоимости любого ребра графа.

Так как вершина k присоединяется к множеству , то вследствие этого изменяются массивы LOWCOST и CLOSEST (строки (13)-(16)).

Программа на языке Pascal, реализующая алгоритм Прима, представлена в листинге 5.2.2. На вход программы поступает матрица стоимостей ребер графа - массив С размера , чьи элементы C[i, j] равны стоимости ребер . Если ребра не существуют, то элемент C[i, j] полагается равным некоторому достаточно большому числу.