Algorithmus von Prim

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Algorithmus von Prim (nach seinem Erfinder Robert C. Prim, 1957) dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.

Inhaltsverzeichnis

1 Algorithmus
2 Vergleich mit dem Algorithmus von Kruskal
3 Effiziente Implementierung
4 Literatur
5 Weblinks

[Bearbeiten] Algorithmus

Der Algorithmus beginnt mit einem trivialen Graphen T, der aus einem beliebigen Knoten des gegebenen Graphen besteht. In jedem Schritt wird nun eine Kante mit minimalem Gewicht gesucht, die einen weiteren Knoten mit T verbindet. Diese und der entsprechende Knoten werden zu T hinzugefügt. Das Ganze wird solange wiederholt, bis alle Knoten in T vorhanden sind; dann ist T ein minimaler Spannbaum:

Wähle einen beliebigen Knoten als Startgraph T.
Solange T noch nicht alle Knoten enthält:

Wähle eine Kante e minimalen Gewichts aus, die einen noch nicht in T enthaltenen Knoten v mit T verbindet.
Füge e und v dem Graphen T hinzu.

Der skizzierte Algorithmus wird durch folgenden Pseudocode beschrieben:

G: Graph
w: Gewichtsfunktion
r: Startknoten (r ∈ V_G)
Q: Prioritätswarteschlange
π[u]: Elternknoten von u im Spannbaum
Adj[u]: Adjazenzliste von u (alle Nachbarknoten)
wert[u]: Abstand von u zum entstehenden Spannbaum

algorithmus_von_prim(G,w,r)
01  Q  V_G   //Initialisierung
02  für alle u ∈ Q
03      wert[u]  ∞
04      π[u]  0
05  wert[r]  0
06  solange Q ≠ 
07      u  extract_min(Q)
08      für alle v ∈ Adj[u]
09          wenn v ∈ Q und w(u,v) < wert[v]
10              dann π[v]  u
11                  wert[v]  w(u,v)

Nachdem der Algorithmus endet, ergibt sich der minimale Spannbaum wie folgt:

$T = \left(V_G, \lbrace\left(u, \pi[u]\right) | u \in V_G - \lbrace r \rbrace\rbrace\right)$

Ein Beispiel zur Arbeitsweise des Algorithmus.

Hier zunächst ein gegebener Beispielgraph:

Als Startknoten wird C gewählt. Nun kann mit der Abarbeitung des Algorithmus begonnen werden:

Nach Abschluss des Algorithmus erhält man nun einen minimalen Spannbaum des Graphen:

[Bearbeiten] Vergleich mit dem Algorithmus von Kruskal

Wie auch der Algorithmus von Kruskal, der ebenfalls einen minimal spannenden Baum konstruiert, ist Prims Algorithmus ein Greedy-Algorithmus. Beide Algorithmen beginnen mit einem Graphen ohne Kanten und fügen in jedem Schritt eine Kante mit minimalem Gewicht hinzu, ohne dabei einen Kreis zu schließen.

Bei Kruskal sind alle Knoten schon zu Beginn vorhanden, so dass der Graph zunächst aus mehreren Zusammenhangskomponenten besteht, die erst im Verlauf des Algorithmus schrittweise durch das Hinzufügen von Kanten verbunden werden. Im Gegensatz dazu ist bei Prims Algorithmus T in jedem Iterationsschritt ein zusammenhängender Graph, der erweitert wird, bis er den gesamten gegebenen Graph aufspannt.

[Bearbeiten] Effiziente Implementierung

Das Geheimnis einer effizienten Implementierung des Algorithmus von Prim liegt darin, möglichst einfach eine Kante zu finden, die man dem entstehenden Baum T hinzufügen kann. Man benötigt also eine Prioritätswarteschlange (Priority Queue), in der alle Knoten gespeichert sind, die noch nicht zu T gehören. Alle Knoten haben einen Wert, der dem der leichtesten Kante entspricht durch die der Knoten mit T verbunden werden kann. Existiert keine solche Kante, wird dem Knoten der Wert ∞ zugewiesen. Die Warteschlange liefert nun immer einen Knoten mit dem kleinsten Wert zurück.

Die Effizienz des Algorithmus hängt infolgedessen von der Implementierung der Warteschlange ab. Bei Verwendung eines Fibonacci-Heaps ergibt sich eine optimale Laufzeit von $O ( | E | + | V | log | V | )$ .

[Bearbeiten] Literatur

R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), S. 1389–1401
D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal on Computing, 5 (Dez. 1976), S. 724–741