|
|
| Line 1: |
Line 1: |
| [[Category:Graph Algorithms]] | | See [http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Prim.html here]. |
| [[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 ==
| |
| | |
| === MST-PRIM(''G,w,r'') ===
| |
| | |
| <code>
| |
| 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)''
| |
| </code>
| |