Prim: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 11: | Line 11: | ||
5 ''Q'' = ''V''[''G''] | 5 ''Q'' = ''V''[''G''] | ||
6 '''while''' ''Q'' ≠ Ø | 6 '''while''' ''Q'' ≠ Ø | ||
7 '''do''' ''u'' = EXTRACT-MIN(''Q'') | 7 '''do''' ''u'' = [[EXTRACT-MIN]](''Q'') | ||
8 '''for''' each v ∈ ''Adj[u]'' | 8 '''for''' each v ∈ ''Adj[u]'' | ||
9 '''do if''' v ∈ ''Q'' and ''w(u,v)'' < ''key''[''v''] | 9 '''do if''' v ∈ ''Q'' and ''w(u,v)'' < ''key''[''v''] | ||
Revision as of 20:20, 29 September 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)