Prim: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Pseudocode == === MST-PRIM(''G,w,r'') === <code> MST-PRIM(''G,w,r'') 1 '''for''' each vertex ''u'' ∈ V[''G''] 2 '''do''' ''key[''u''] = ∞ 3...") |
|||
| Line 5: | Line 5: | ||
<code> | <code> | ||
MST-PRIM(''G,w,r'') | MST-PRIM(''G,w,r'') | ||
1 '''for''' each vertex ''u'' ∈ V[''G''] | 1 '''for''' each vertex ''u'' ∈ ''V''[''G''] | ||
2 '''do''' ''key[''u''] = ∞ | 2 '''do''' ''key''[''u''] = ∞ | ||
3 π[''u''] = NIL | 3 π[''u''] = NIL | ||
4 ''key[r] = 0 | 4 ''key''[''r''] = 0 | ||
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''] | ||
10 '''then''' π[''v''] = ''u'' | 10 '''then''' π[''v''] = ''u'' | ||
11 ''key[v] = ''w(u,v)'' | 11 ''key''[''v''] = ''w(u,v)'' | ||
</code> | </code> | ||
Revision as of 18:34, 25 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)