Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Algorithmus von Prim aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

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.

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 $\backslash leftarrow$ V_G //Initialisierung
02 für alle u ? Q
03 wert[u] $\backslash leftarrow$ ?
04 ?[u] $\backslash leftarrow$ 0
05 wert[r] $\backslash leftarrow$ 0
06 solange Q ? $\backslash varnothing$
07 u $\backslash leftarrow$ extract_min(Q)
08 für alle v ? Adj[u]
09 wenn v ? Q und w(u,v) < wert[v]
10 dann ?[v] $\backslash leftarrow$ u
11 wert[v] $\backslash leftarrow$ w(u,v)
Nachdem der Algorithmus endet, ergibt sich der minimale Spannbaum wie folgt:
:$T\; =\; \backslash left(V\_G,\; \backslash lbrace\backslash left(u,\; \backslash pi[u]\backslash right)\; /\text{'}>\; u\; \backslash in\; V\_G\; -\; \backslash lbrace\; r\; \backslash rbrace\backslash rbrace\backslash right)$

Ein Beispiel zur Arbeitsweise des 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. Bei Verwendung eines Fibonacci-Heaps ergibt sich eine optimale Laufzeit von $O(|E|\; +\; |V|\; \backslash log\; |V|)$.

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

Weblinks

• Minimum Spanning Tree und 2-Approximation der TSP-Tour, Michael Daumen, 2000
• Interaktives Java-Applet zur Demonstration

       VIDEO-NEWS UND ANGEBOTE