Algorithmus von Prim

Der Algorithmus wird schrittweise verfeinert und der Aufbau eines aufgespannten Baumes erfolgt durch das Hinzufügen von Kanten. Das Greedy Muster, also jeweils die Wahl der kostengünstigsten Kante als Erweiterung, wird hier benutzt.

Aufspannender minimaler Baum

//Teilbaum B besteht anfangs aus einem beliebigen Knoten
while [ B noch nicht GV aufspannt ]
do [ suche kostengünstige von B ausgehende Kante ];
     [ füge diese Kante zu B hinzu ];
od

Eine Verfeinerung der Suche nach der kostengünstigsten Kante ist notwendig!

Suche nach kostengünstigster Kante

Die intuitive Vorgehensweise erfordert jeweils |W|(|V|-|W|) Vergleiche für ein gegebenes W. Das ganze |V| mal, also eine Gesamtlaufzeit von $O(n^{3})$ . Man kann die Suche auf die Teilmengen $F\subseteq E$ beschränken, so dass F immer die günstigste aus b ausgehende Kante enthält, wesentlich weniger Kanten hat als |W|(|V|-|W|) und im Verlauf des Algorithmus einfach anpassbar ist.

Wahl von F

Alternativen:

a) F enthält für jeden Knoten v in B die günstigste von v aus B herausführende Kante

b) F enthält für jeden Knoten v außerhalb B die günstigste von v in B hineinführende Kante

Bewertung:

a) Mehrere Kanten können zum gleichen Knoten herausführen – redundant und änderungsaufwändig (bei Wahl dieses Knotens darf er nicht mehr verwendet werden und alle Verbindungen zu diesem Knoten müssen gelöscht werden)

b) Daher: Wahl von b)

Erste Verfeinerung

// Teilbaum B 
		[ B:= ({ beliebiger Knoten v }, {}) ]

		// Menge der Kandidatenkanten F
		[ F:= alle nach v führenden Kanten ]

		// alle Knoten betrachten
		for i := 1 to |V|-1
		do 	[ suche günstigste Kante f=(u,w) in F ];
			[ Füge f zu B hinzu (natürlich auch w) ];
		     	[ Aktualisiere F ];
		od

F muss nach jedem Durchlauf angepasst werden. Wenn f aus F entfernt wird erkennt man, dass der Teilgraph B tatsächlich ein Baum ist. Nun haben wir den neu verbundenen Knoten w. Jeder noch nicht verbundene Knoten x hat nun eine günstigste Verbindung entweder wie zuvor, oder aber mit dem neu hinzugefügten Knoten w!

Zweite Verfeinerung

// Teilbaum B 
		[ B:= ({ beliebiger Knoten v },{}) ]
		// Menge der Kandidatenkanten F
		[ F:= alle nach v führenden Kanten ]
		
		for i := 1 to |V|-1
		do 	
			// Sei v∈B, w∈B
			[ suche günstigste Kante f=(v,w) in F ];
			[ Füge f zu B hinzu ];
			// Aktualisiere F	
		     	[ Entferne f aus F ];
			// x in B, w neuerdings in B, y noch nicht in B
			for [ alle Kanten e=(x,y)∈F]
			do 
				if [ c((w,y))<c(e)] then [ Ersetze e durch (w,y) ] fi
			od	
		od

Kommunikationsnetz

i:

$B_{0}=(\{A\},\{\})$

$F_{0}=\{(A,E),(A,D),(A,C),(A,B)\}$

$f_{1}=(A,E)$ ist am günstigsten

$B_{1}=(\{A,E\},\{(A,E)\})$

$F_{1}=\{(A,D),(A,C),(A,B)\}$

$(A,D):F_{1}^{1}=\{(D,E),(A,C),(A,B)\}$

$(A,C):F_{1}^{2}=\{(D,E),(C,E),(A,B)\}$

$(A,B):F_{1}^{3}=\{(D,E),(C,E),(B,E)\}$

$f_{2}=(E,B)$

….

Analyse

Terminierungstheorem

Der Algorithmus von Prim terminiert nach endlicher Zeit.

Beweis

Einfache Schleifenanalyse

Laufzeittheorem

Wird für die Implementierung von F ein Fibonacci‐Heap benutzt, so hat der Algorithmus von Prim eine Laufzeit von O(|E| + |V| log |V|).

Korrektheitstheorem

Ist G ein verbundener ungerichteter gewichteter Graph, so berechnet der Algorithmus von Prim einen minimalen Spannbaum von G.

Beweis

Wir betrachten eine einfache Version des Algorithmus.

while [ B noch nicht GV aufspannt ]
do [ suche kostengünstige von B ausgehende Kante ]; 
     [ füge diese Kante zu B hinzu ];
od

Wir beobachten, dass B am Ende ein Spannbaum ist. Jetzt ist noch zu zeigen, dass B am Ende ein minimaler Spannbaum ist.

Sei B‘ ein minimaler Spannbaum von G und B≠B‘. Betrachte den Zeitpunkt in der Hauptschleife, an dem sich die Konstruktion von B von B‘ unterscheidet. Sei e die Kante, die dann zu B hinzugefügt wird. Sei $V_{1}$ die Menge der Knoten, die schon in B sind und $V_{2}=V$ \ $V_{1}$ Da B‘ ein minimaler Spannbaum ist, gibt es eine Kante e', die $V_{1}$ mit $V_{2}$ verbindet. Da im Algorithmus stets eine günstigste Kante gewählt wird, muss gelten g(e)≤g(e‘). Tauschen wir in B‘ die Kante e‘ durch e erhalten wir also einen minimalen Spannbaum, der nicht mehr kostet als B‘, es folgt g(e)=g(e‘). Induktiv folgt damit die Korrektheit.