3622
правки
Изменения
→Реализация: псевдокод в \mathtt
<font color=green>// <tex>G</tex> {{---}} исходный граф</font>
<font color=green>// <tex>w</tex> {{---}} весовая функция</font>
'''function''' <tex>\mathtt{primFindMST}():</tex> '''for''' <tex>v '''\in''' V(G)</tex> <tex>\mathtt{key}[v] \ = <tex>\ \infty</tex> <tex>\mathtt{p}[v] \ = </tex> ''null'' <tex>r \ = </tex> произвольная вершина графа <tex>G</tex> <tex>\mathtt{key}[r] \ = \ \mathtt{0 }</tex> <tex>Q.\mathrm{push}(V(G) )</tex> '''while not''' <tex>Q.\mathtt{isEmpty}()</tex> <tex>v \ = \ Q.\mathtt{extractMin}() </tex> '''for''' <tex>vu '''\in''' E(G)</tex> '''if''' <tex>u '''\in''' Q </tex> '''and''' <tex>\mathtt{key}[u] > w(v, u)</tex> <tex>\mathtt{p}[u] \ = \ v</tex> <tex>\mathtt{key}[u] \ = \ w(v, u)</tex> <tex>Q.\mathrm{decreaseKey}(u, \mathtt{key}[u])</tex>
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>
