Prim

From Algowiki
Revision as of 20:20, 29 September 2014 by Luedecke (talk | contribs)
Jump to navigation Jump to search

Pseudocode

MST-PRIM(G,w,r)

MST-PRIM(G,w,r)

 1  for each vertex uV[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)