next up previous contents
Next: Kruskals Algorithmus Up: Minimale Spannbäume Previous: Konstruktion von minimalen Spannbäumen

Generischer minimaler Spannbaum-Algorithmus 




Initialisiere Wald F von Bäumen, jeder Baum ist ein singulärer Knoten.
(jedes $v\in V$ bildet einen Baum) 
while Wald F mehr als einen Baum enthält do
		 wähle einen Baum $T \in F$ aus;
		 bestimme eine leichteste Kante $e=\{v,w\}$ aus T heraus;
		 sei $v\in T, w\in T'$;		 vereinige T und T', füge e zum minimalen Spannbaum hinzu;
od


\begin{picture} (85,70) \multiput(35,0)(0,2){36}{\line(0,1){1}} \put(50,15){\c... ...olor {red} \bezier{40}(25,50)(35,47.5)(45,45) \color {black} \end{picture}



Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999