logo
УП_САОД_2003

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

В этом алгоритме строится множество вершин U, из которого «вырастает» остовное дерево.

Сначала U = . На каждом шаге алгоритма находится ребро наименьшей стоимости (u, v) такое, что u  U, v  V\U, затем вершина v переносится из V\U в U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V.

Рисунок 58. Алгоритм Прима

U := ;

U:= U  любая вершина;

while V\U <>  do begin

Выбрать ребро (u, v) наименьшей стоимости, где uU, vV\U;

U:= U  v;

V\U := (V\U)  v;

end;

Очевидно, данный алгоритм для графа с n вершинами имеет сложность, пропорциональную O(n2)

        1.