Prim: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
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'' &isin; ''V''[''G'']
  2      '''do''' ''key''[''u''] = &infin;
  3                &pi;[''u''] = NIL
  4  ''key''[''r''] = 0
  5  ''Q'' = ''V''[''G'']
  6  '''while''' ''Q'' &ne; &Oslash;
  7      '''do''' ''u'' = [[EXTRACT-MIN]](''Q'')
  8                '''for''' each v &isin; ''Adj[u]''
  9                      '''do if''' v &isin; ''Q'' and ''w(u,v)'' < ''key''[''v'']
10                              '''then''' &pi;[''v''] = ''u''
11                                      ''key''[''v''] = ''w(u,v)''
</code>

Revision as of 12:25, 16 June 2015

See here.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Prim&oldid=3307"