Algorithmus von Prim

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

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.

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.

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. Eine geeignete Datenstruktur ist der Heap. Durch die Verwendung eines Fibonacci-Heaps ergibt sich für dichte Graphen eine optimale Laufzeit von O(|E| + |V| log |V|).

Der oben skizzierte Algorithmus wird durch folgenden Pseudocode beschrieben:

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

algorithmus_von_prim(G,w,r)
01  Q $\leftarrow$ VG - {r}   //Initialisierung
02  für alle u ∈ Q
03      führe aus wert[u] $\leftarrow$ ∞
04          π[u] $\leftarrow$ 0
05  π[r] $\leftarrow$ 0
06  solange Q ≠ $\varnothing$
07      führe aus u $\leftarrow$ extract_min(Q)
08          für alle v ∈ Adj[u]
09              führe aus wenn v ∈ Q und w(u,v) < wert[v]
10                  dann π[v] $\leftarrow$ u
11                      wert[v] $\leftarrow$ 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)$

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 of Computing, 5 (Dez. 1976), S. 724–741

Siehe auch

• Algorithmus von Kruskal
• Minimum Spanning Tree und 2-Approximation der TSP-Tour, Michael Daumen, 2000