Kurs:Algorithmen und Datenstrukturen/Vorlesung/Algorithmus von Prim




Algorithmus von PrimBearbeiten

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 BaumBearbeiten

//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 KanteBearbeiten

Die intuitive Vorgehensweise erfordert jeweils |W|(|V|-|W|) Vergleiche für ein gegebenes W. Das ganze |V| mal, also eine Gesamtlaufzeit von  . Man kann die Suche auf die Teilmengen   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 FBearbeiten

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 VerfeinerungBearbeiten

// 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 VerfeinerungBearbeiten

// 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

KommunikationsnetzBearbeiten

i:

 

 

  ist am günstigsten

 

 

 

 

 

 

….

AnalyseBearbeiten

TerminierungstheoremBearbeiten

Der Algorithmus von Prim terminiert nach endlicher  Zeit. 

BeweisBearbeiten

Einfache Schleifenanalyse

LaufzeittheoremBearbeiten

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|). 

KorrektheitstheoremBearbeiten

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

BeweisBearbeiten

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   die Menge der Knoten, die schon in B sind und   \   Da B‘ ein minimaler Spannbaum ist, gibt es eine Kante e', die   mit   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.