Изменения
→Реализация
== Реализация ==
'''<tex>\text{MST\_PrimPrim}(V, G, w)</tex>''' '''<tex>for''' (для) всех </tex> <tex>v \in V[G]</tex> '''<tex>do''' </tex> <tex> key[v] \leftarrow \infty </tex>
<tex>p[v] \leftarrow \text{NIL}</tex>
<tex>r \leftarrow </tex> <tex> произвольная вершина в </tex><tex>V[G]</tex>
<tex>key[r] \leftarrow 0 </tex>
<tex>Q \leftarrow V[G] </tex>
<tex>key[v] \leftarrow \omega(u, v)</tex>
<tex>\text{DECREASE-KEY}(Q, v) </tex>
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.
== Корректность ==
По поддерживаемым инвариантам после извлечения вершины <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> раз, корректен.
