next up previous contents
Next: Prim's Algorithmus, zweite Variante Up: Grundlagen Previous: Kruskals Algorithmus

Prim's Algorithmus, erste Variante 



algorithm PRIM-MSB (G,w):= 
$\ulcorner$ 
		 initialisiere Priority Queue PQ mit Knotenmenge V und Schlüssel $+\infty, \forall v \in V$;		 wähle Knoten r als Wurzel (beliebig);
		 Schlüssel[r] := 0;
		 Vorgänger$[r] :=\ $nil;
		 while $PQ \neq \emptyset$ do
		 		 u:=    FindMin(PQ);
		 		    DeleteMin(PQ);
		 		 for alle Knoten v, die in G zu u benachbart sind do
		 		 		 if $v \in PQ$ and w$(\{u,v\})<$ Schlüssel[v] then
		 		 		 		 Vorgänger[v]:=u;
		 		 		 		 Schlüssel[v]:= w$(\{u,v\})$;		 		 		 fi
		 		 od
		 od 
$\llcorner$
Beispiel für Prim's Algorithmus (erste Variante):
\includegraphics {eps/3_11.eps}
\includegraphics {eps/3_12.eps}
\includegraphics {eps/3_13.eps}
\includegraphics {eps/3_14.eps}
\includegraphics {eps/3_15.eps}
\includegraphics {eps/3_16.eps}
\includegraphics {eps/3_17.eps}
\includegraphics {eps/3_18.eps}
\includegraphics {eps/3_19.eps}
\includegraphics {eps/3_20.eps}
Korrektheit: ist klar.
Zeitkomplexität: Implementierung der Priority Queue mittels Fibonacci-Heaps:

Initialisierung $\mathcal{O}(n)$
Find + DeleteMins $\mathcal{O}(m)\quad(\leq m$ Stück)
DecreaseKeys $\mathcal{O}(m)\quad(\leq m$ Stück)
Sonstige Overhead $\mathcal{O}(1)$


$ \Rightarrow $ Laufzeit:
\fbox {$\leadsto \mathcal{O}(n)+\mathcal{O}(n \log(n))+m \cdot \mathcal{O}(1)+m \cdot \mathcal{O}(1)=\mathcal{O}(m+n \log n)$}


\fbox {\parbox[c]{12.45cm}{\noindent\textbf{Satz:} Sei $G=(V,E)$\space ein unger... ...t$). Dies ist f\uml {u}r $m = \Omega(n \log n)$\space asymptotisch optimal. }}


Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999