Изменения
Нет описания правки
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.
== Корректность ==
По поддерживаемым инвариантам после извлечения вершины <tex>v</tex> (<tex>v \neq r</tex>) из <tex>Q</tex> ребро <tex>\left(v,p(v)\right)</tex> является ребром минимального веса, пересекающим разрез <tex>\left(F,Q\right)</tex>. Значит, по [[Лемма о безопасном ребре|лемме о безопасном ребре]], оно безопасно. Алгоритм построения MST, добавляющий безопасные ребра, причём делающий это ровно <tex>|V|-1</tex> раз, корректен.
== Оценка производительности ==
Производительность алгоритма Прима зависит от выбранной реализации приоритетной очереди, как и в [[алгоритм Дейкстры|алгоритме Дейкстры]]. Извлечение минимума выполняется <tex>V</tex> раз, релаксация — <tex>O(E)</tex> раз.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных для приоритетной очереди
!style="background:#f2f2f2"|Асимптотика времени работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|Двоичная куча
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|Куча Фибоначчи
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}
==Пример работы алгоритма==
[[Файл:Prim1.jpg|right|400px|thumb|Граф "звезда" с расставленными весами ребер ]]
|style="background:#FF0000"|71
|style="background:#f9f9f9"|5 2 4 1 3
|}
