Prim-Algorithmus
Stellen Sie sich vor, Sie verlegen Kabel von einem Kraftwerk aus: Sie schließen zuerst die nächste Stadt an, dann die Stadt, die irgendeinem schon angeschlossenen Ort am nächsten liegt, und so weiter. Das ist der Prim-Algorithmus, und er endet immer mit dem günstigsten möglichen Netz.
Die Idee
Ein minimaler Spannbaum verbindet alle Knoten eines gewichteten Graphen mit der kleinstmöglichen Gesamtlänge der Kanten. Der Prim-Algorithmus baut ihn, indem er einen Baum von einem Start aus nach außen wachsen lässt. Der Baum zerfällt nie in Teile: In jedem Schritt kommt genau ein neuer Knoten dazu, über die kürzeste Kante, die aus dem Baum herausführt.
Schritt für Schritt
Setzen Sie den Start in den Baum. Merken Sie sich für jeden Knoten außerhalb des Baums seine beste Kante: seine kürzeste Kante zu irgendeinem Knoten im Baum. Dann wiederholen Sie: Wählen Sie den äußeren Knoten mit der kürzesten besten Kante, fügen Sie ihn mit dieser Kante zum Baum hinzu und prüfen Sie seine Kanten. Ein Nachbar außerhalb des Baums, der jetzt über eine kürzere Kante erreichbar ist, bekommt diese Kante als neue beste. Schluss ist, wenn alle Knoten im Baum sind.
Ein Beispiel
Nehmen Sie die Kanten A–B mit Länge 1, B–C 2, A–C 3, C–D 4 und B–D 5 und beginnen Sie bei A. Die Kanten von A geben B die beste Kante 1 und C die beste Kante 3. B ist am nächsten, also kommt B über A–B dazu; seine Kanten verbessern C auf 2 und geben D 5. C kommt über B–C dazu, und seine Kante C–D verbessert D auf 4. Zum Schluss kommt D über C–D dazu. Der Baum A–B, B–C, C–D hat die Gesamtlänge 1 + 2 + 4 = 7.
Warum er korrekt ist
In jedem Schritt sind die Knoten in zwei Gruppen geteilt: die im Baum und die außerhalb. Die Schnitteigenschaft besagt, dass die kürzeste Kante zwischen zwei solchen Gruppen immer zu einem minimalen Spannbaum gehört. Prim fügt immer genau diese Kante hinzu, also lässt sich der bisher gebaute Baum immer zu einem minimalen Spannbaum ergänzen, und wenn alle Knoten dazugekommen sind, ist er einer.
Geschichte und Aufwand
Der tschechische Mathematiker Vojtěch Jarník veröffentlichte den Algorithmus 1930. Robert Prim entdeckte ihn 1957 bei den Bell Labs wieder, Edsger Dijkstra erneut 1959. Mit den wartenden Knoten in einem binären Heap wächst der Aufwand mit E log V, bei V Knoten und E Kanten; mit einem einfachen Array sind es etwa V², was besser ist, wenn fast jedes Knotenpaar verbunden ist. Mit einem Fibonacci-Heap sind es E + V log V.
Selbst ausprobieren
Öffnen Sie die App, klicken Sie auf einen Knoten, um dort zu beginnen, und drücken Sie Schritt. Knoten im Baum sind grün, wartende Knoten blau, und die beste Kante jedes wartenden Knotens ist gestrichelt. Die wartenden Knoten stehen unter dem Graphen mit der Länge ihrer besten Kante, die kürzeste zuerst: Der erste kommt als Nächstes dazu. Beginnen Sie bei verschiedenen Knoten und sehen Sie, wie sich die Reihenfolge ändert, während die Gesamtlänge gleich bleibt.
Häufig gestellte Fragen
Was ist der Unterschied zwischen dem Prim- und dem Dijkstra-Algorithmus?
Beide lassen mit einer Prioritätswarteschlange ein Gebiet von einem Start aus wachsen. Prim ordnet einen wartenden Knoten nach der Länge seiner einen besten Kante zum Baum, Dijkstra nach seinem ganzen Abstand vom Start. Prim liefert einen minimalen Spannbaum, Dijkstra einen Baum kürzester Wege.
Funktioniert der Prim-Algorithmus mit negativen Kantenlängen?
Ja. Anders als der Dijkstra-Algorithmus vergleicht Prim nur Kanten miteinander, also machen negative Längen keine Probleme: Er findet trotzdem einen Spannbaum mit der kleinsten Gesamtlänge.
Was, wenn der Graph nicht zusammenhängend ist?
Dann hört der Prim-Algorithmus auf, sobald er jeden Knoten erreicht hat, den er erreichen kann: Er liefert nur einen minimalen Spannbaum für den Teil des Graphen, in dem der Start liegt. Startet man ihn erneut bei einem noch nicht erreichten Knoten, erhält man einen minimalen Spannwald.
Ist der Prim- oder der Kruskal-Algorithmus besser?
Keiner gewinnt immer. Prim eignet sich für dichte Graphen und für Graphen, die als Nachbarlisten gespeichert sind, Kruskal für dünne Graphen, die als Kantenliste vorliegen. Beide finden einen Baum mit derselben Gesamtlänge.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Prim-Algorithmus ausprobieren