Algorithmus von Prim

Auf dieser Seite wird der Algorithmus von Prim behandelt.

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, wir 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