Algorithmus von Prim

Zweck und Grundidee

Der Algorithmus von Prim berechnet in einem zusammenhängenden, ungerichteten und kantengewichteten Graphen einen minimalen Spannbaum. Ein Spannbaum verbindet alle Knoten des Graphen ohne Kreise; „minimal“ bedeutet, dass die Summe seiner Kantengewichte möglichst klein ist.

Er beginnt mit einem beliebigen einzelnen Startknoten als Teilgraph T. Danach wird wiederholt die leichteste Kante gewählt, die einen Knoten in T mit einem Knoten außerhalb von T verbindet. Diese Kante und ihr neuer Knoten werden zu T hinzugefügt. Sobald T alle Knoten enthält, ist T ein minimaler Spannbaum. Die Auswahl einer Kante über die Grenze zwischen dem bisherigen Baum und den übrigen Knoten verhindert dabei automatisch Kreise.

Ablauf mit Prioritätswarteschlange

Für die Umsetzung speichert eine Prioritätswarteschlange Q alle noch nicht aufgenommenen Knoten. Für jeden Knoten u bezeichnet wert[u] das Gewicht der derzeit leichtesten Kante, durch die u an den entstehenden Baum angeschlossen werden kann; zunächst gilt wert[u] = ∞. π[u] speichert den Elternknoten von u im Spannbaum.

Der Startknoten r erhält wert[r] = 0. Solange Q nicht leer ist, wird mit extract_min(Q) ein Knoten u mit dem kleinsten Wert entnommen. Für jeden Nachbarn v von u wird geprüft: Ist v noch in Q und gilt w(u,v) < wert[v], dann werden π[v] = u und wert[v] = w(u,v) gesetzt. Nach dem Ende besteht der Spannbaum aus T = (V_G, {(u, π[u]) | u ∈ V_G \ {r}}).

Dabei ist w die Gewichtsfunktion der Kanten und Adj[u] die Adjazenzliste, also die Liste der Nachbarn von u.

Beispielhafte Auswahl der Kanten

Im dargestellten Beispiel wird D als Startknoten gewählt; jeder andere Knoten wäre ebenfalls möglich. Zuerst sind die Kanten DA, DB, DE und DF mögliche Anschlüsse. DA hat das kleinste Gewicht und wird mit A aufgenommen.

Danach wird unter AB, DB, DE und DF die Kante DF gewählt und F hinzugefügt. Anschließend folgen jeweils die leichtesten möglichen Anschlusskanten AB mit B, BE mit E, EC mit C und schließlich EG mit G. Der Baum enthält dann alle Knoten und ist ein minimaler Spannbaum des Ausgangsgraphen.

Effizienz und Laufzeit

Entscheidend für die Effizienz ist, wie schnell der Knoten mit der günstigsten Verbindung zum bisherigen Baum gefunden wird. Die Prioritätswarteschlange enthält dazu alle Knoten außerhalb von T und ordnet sie nach ihrem aktuellen Wert. Gibt es noch keine Verbindung zu T, bleibt ihr Wert ∞.

Insgesamt führt der Algorithmus |V| extractMin-Operationen und |E| decreaseKey-Operationen aus. Mit einem Fibonacci-Heap kostet extractMin amortisiert O(log |V|) und decreaseKey amortisiert O(1). Damit beträgt die Gesamtlaufzeit O(|E| + |V| · log |V|), auch geschrieben O(|E|+|V|log |V|).

Warum das Ergebnis minimal ist

Da der Ausgangsgraph zusammenhängend ist, gibt es in jeder Iteration eine Kante vom bereits aufgebauten Teilgraphen zu einem noch nicht aufgenommenen Knoten. Weil jeweils genau ein neuer Knoten zusammen mit einer verbindenden Kante ergänzt wird, entsteht ein Baum.

Zum Nachweis der Minimalität betrachtet man einen minimalen Spannbaum T₁. Falls eine vom Prim-Algorithmus zuerst gewählte Kante e nicht in T₁ liegt, verbindet e die bereits verbundenen Knoten V mit einem Knoten außerhalb von V. Im Spannbaum T₁ gibt es zwischen den Endknoten von e einen Pfad; auf ihm liegt eine Kante f, die ebenfalls von V nach außerhalb führt. Da Prim e als leichteste mögliche Kante auswählt, ist das Gewicht von f mindestens so groß wie das von e.

Ersetzt man in T₁ die Kante f durch e, entsteht wieder ein zusammenhängender Baum T₂ mit derselben Zahl von Kanten und keinem größeren Gesamtgewicht. T₂ ist daher ebenfalls minimal und enthält nun die bisher gewählten Kanten. Durch Wiederholung zeigt sich, dass der von Prim erzeugte Baum selbst ein minimaler Spannbaum ist.

Vergleich, Parallelisierung und Programmierung

Wie der Algorithmus von Kruskal ist Prim ein Greedy-Algorithmus: In jedem Schritt wird eine Kante mit minimalem Gewicht ergänzt. Kruskal sucht global nach leichten Kanten und muss Kreisbildung aktiv verhindern. Prim betrachtet nur Kanten vom bisherigen Teilbaum zur übrigen Knotenmenge; deshalb können bei ihm per Konstruktion keine Kreise entstehen. Ein direkter Laufzeitvergleich ist schwierig: Bei Prim bestimmen vor allem die Knoten die Komplexität, bei Kruskal dominiert die sortierte Kantenliste und damit die Zahl der Kanten.

Die äußere Schleife von Prim ist grundsätzlich sequentiell, weil die aktuell leichteste Schnittkante sich nach jeder Aufnahme ändern kann. Auf einer Parallel Random Access Machine mit O(|V|) Prozessoren kann der Zugriff auf die Prioritätswarteschlange beschleunigt werden; dann ergibt sich O(|E|+|V|). Bei einer weiteren Variante verwaltet jeder Prozessor einen Teil Vᵢ der Knoten und einen Kostenvektor C. Pro Iteration werden lokale Minima bestimmt, per Minimum-Reduktion ein globales Minimum ausgewählt, an alle Prozessoren übertragen und die Kosten aktualisiert. Ihre Laufzeit ist O(|V|²/|P|) + O(|V|log |P|). Sie kann auf verteilten Systemen, Shared-Memory-Systemen und Grafikprozessoren eingesetzt werden; Borůvkas Algorithmus eignet sich im Allgemeinen besser zur Parallelisierung.

Das C#-Beispiel speichert die Kantengewichte in einer zweidimensionalen Integer-Matrix. Ein Array includedNodes markiert bereits aufgenommene Knoten, distances enthält die aktuellen kleinsten Anschlussgewichte und parent den jeweiligen Elternknoten. GetMinimumIndex wählt den noch nicht aufgenommenen Knoten mit kleinstem Abstand; anschließend werden die möglichen Anschlüsse seiner Nachbarn aktualisiert. Zum Schluss werden die Kanten parent[i] - i und ihre Abstände ausgegeben.