Prim: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Category:Graph Algorithms]] | |||
[[Category:Minimal Spanning Tree]] | |||
<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;"> | |||
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Prim</div> | |||
<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div> | |||
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/prim-2431 Openlearnware]</div> | |||
</div> | |||
== Pseudocode == | == Pseudocode == | ||
Revision as of 10:16, 1 October 2014
Pseudocode
MST-PRIM(G,w,r)
MST-PRIM(G,w,r)
1 for each vertex u ∈ V[G]
2 do key[u] = ∞
3 π[u] = NIL
4 key[r] = 0
5 Q = V[G]
6 while Q ≠ Ø
7 do u = EXTRACT-MIN(Q)
8 for each v ∈ Adj[u]
9 do if v ∈ Q and w(u,v) < key[v]
10 then π[v] = u
11 key[v] = w(u,v)