Prim

Prim

whatever

Openlearnware

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)