Algorithmus von Prim - LinkFang.de





Algorithmus von Prim


Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.

Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er zunächst von Robert C. Prim und dann 1959 von Edsger W. Dijkstra wiederentdeckt. Daher wird der Algorithmus in der Literatur auch gelegentlich unter anderen Namen geführt, so etwa Prim-Dijkstra-Algorithmus oder Algorithmus von Jarnik, Prim und Dijkstra, im englischen Sprachraum auch Jarnik's algorithm oder DJP algorithm.

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 mit minimalem Gewicht 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
VG: Knotenmenge von G
w: Gewichtsfunktion für Kantenlänge
r: Startknoten (r ∈ VG)
Q: Prioritätswarteschlange
π[u]: Elternknoten von Knoten 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 [math]\leftarrow[/math] VG   //Initialisierung
02  für alle u ∈ Q
03      wert[u] [math]\leftarrow[/math] ∞
04      π[u] [math]\leftarrow[/math] 0
05  wert[r] [math]\leftarrow[/math] 0
06  solange Q ≠ [math]\varnothing[/math]
07      u [math]\leftarrow[/math] extract_min(Q)
08      für alle v ∈ Adj[u]
09          wenn v ∈ Q und w(u,v) < wert[v]
10              dann π[v] [math]\leftarrow[/math] u
11                  wert[v] [math]\leftarrow[/math] w(u,v)

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

[math]T = \left(V_G, \lbrace\left(u, \pi[u]\right) | u \in V_G \backslash \lbrace r \rbrace\rbrace\right)[/math]

Beispiel

In diesem Beispiel wird der Ablauf des Algorithmus von Prim an einem einfachen Graphen gezeigt. Der Zwischenbaum [math]T[/math] ist jeweils grün hervorgehoben. Alle Knoten, die im jeweiligen Schritt über eine einzelne Kante mit dem Graphen verbunden werden können, sind zusammen mit der jeweiligen Kante geringsten Gewichts blau hervorgehoben. Der Knoten und die Kante, die hinzugefügt werden, sind hellblau markiert.

Dies ist der Graph, zu dem der Algorithmus von Prim einen minimalen Spannbaum berechnen wird. Die Zahlen bei den einzelnen Kanten geben das jeweilige Kantengewicht an.
Als Startknoten für den Graphen [math]T[/math] wird der Knoten [math]D[/math] gewählt. (Es könnte auch jeder andere Knoten ausgewählt werden.) Mit dem Startknoten können die Knoten [math]A[/math], [math]B[/math], [math]E[/math] und [math]F[/math] jeweils unmittelbar durch die Kanten [math]DA[/math], [math]DB[/math], [math]DE[/math] und [math]DF[/math] verbunden werden. Unter diesen Kanten ist [math]DA[/math] diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten [math]A[/math] zum Graphen [math]T[/math] hinzugefügt.
Mit dem bestehenden Graphen [math]T[/math] kann der Knoten [math]B[/math] durch die Kanten [math]AB[/math] oder [math]DB[/math], der Knoten [math]E[/math] durch die Kante [math]DE[/math] und der Knoten [math]F[/math] durch die Kante [math]DF[/math] verbunden werden. Unter diesen vier Kanten ist [math]DF[/math] diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten [math]F[/math] zum Graphen [math]T[/math] hinzugefügt.
Mit dem bestehenden Graphen [math]T[/math] kann der Knoten [math]B[/math] durch die Kanten [math]AB[/math] oder [math]DB[/math], der Knoten [math]E[/math] durch die Kanten [math]DE[/math] oder [math]FE[/math] und der Knoten [math]G[/math] durch die Kante [math]FG[/math] verbunden werden. Unter diesen Kanten ist [math]AB[/math] diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten [math]B[/math] zum Graphen [math]T[/math] hinzugefügt.
Mit dem bestehenden Graphen [math]T[/math] kann der Knoten [math]C[/math] durch die Kante [math]BC[/math], der Knoten [math]E[/math] durch die Kanten [math]BE[/math], [math]DE[/math] oder [math]FE[/math] und der Knoten [math]G[/math] durch die Kante [math]FG[/math] verbunden werden. Unter diesen Kanten ist [math]BE[/math] diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten [math]E[/math] zum Graphen [math]T[/math] hinzugefügt.
Mit dem bestehenden Graphen [math]T[/math] kann der Knoten [math]C[/math] durch die Kanten [math]BC[/math] oder [math]EC[/math] und der Knoten [math]G[/math] durch die Kanten [math]EG[/math] oder [math]FG[/math] verbunden werden. Unter diesen Kanten ist [math]EC[/math] diejenige mit dem geringsten Gewicht und wird deshalb zusammen mit dem Knoten [math]C[/math] zum Graphen [math]T[/math] hinzugefügt.
Der verbliebene Knoten [math]G[/math] kann durch die Kanten [math]EG[/math] oder [math]FG[/math] mit dem Graphen [math]T[/math] verbunden werden. Da [math]EG[/math] unter diesen beiden das geringere Gewicht hat, wird sie zusammen mit dem Knoten [math]G[/math] zum Graphen [math]T[/math] hinzugefügt.
Der Graph [math]T[/math] enthält jetzt alle Knoten des Ausgangsgraphen und ist ein minimaler Spannbaum dieses Ausgangsgraphen.

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. Sie unterscheiden sich vor allem darin, wie die Bildung eines Kreises vermieden wird.

Während Kruskals Algorithmus global nach möglichen besten (d. h. leichtesten) Kanten sucht und bei der Aufnahme dieser Kanten in den Lösungssubgraph die Kreisbildung aktiv vermeidet, betrachtet der Algorithmus von Prim nur Kanten, die von den Knoten der bisher konstruierten Teilknotenmenge zu Knoten der Komplementärmenge verlaufen. Da aus dieser (lokalen) Kantenmenge eine Kante ausgewählt wird, vermeidet der Algorithmus per Konstruktion das Auftreten von Kreisen.

Ein Vergleich der beiden Algorithmen auf Basis der Komplexität ist schwierig, da im Algorithmus von Prim die Knoten die zentrale Komplexitätsschranke bestimmen, während Kruskals Algorithmus auf Basis einer sortierten Kantenliste arbeitet und daher dessen Laufzeit von der Anzahl der Kanten dominiert wird.[1]

Effiziente Implementierung

Für eine effiziente Implementierung des Algorithmus von Prim muss man möglichst einfach eine Kante 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 [math]\infty[/math] 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 [math]\mathcal{O}(|E| + |V| \log |V|)[/math].

Literatur

  • Robert C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), S. 1389–1401
  • David Cheriton, Robert Tarjan: Finding minimum spanning trees. In: SIAM Journal on Computing, 5 (Dez. 1976), S. 724–741
  • Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. In: Computer Science Press, 1978, S. 174–183

Weblinks

 Commons: Algorithmus von Prim  – Sammlung von Bildern, Videos und Audiodateien
 Wikibooks: Algorithmus von Prim – Implementierungen in der Algorithmensammlung

Einzelnachweise

  1. vergl. dazu etwa Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. (s. Literatur)

Kategorien: Optimierungsalgorithmus | Graphsuchalgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Algorithmus von Prim (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.