- Aktuell
- Im Baum
- Neben dem Baum
- Bisher beste Kante
Prim-Algorithmus
Der Prim-Algorithmus baut einen minimalen Spannbaum, also die günstigste Menge von Kanten, die alle Knoten verbindet, indem er einen einzigen Baum von einem Start aus wachsen lässt. In jedem Schritt fügt er den Knoten hinzu, der vom Baum aus über die kürzeste Kante erreichbar ist. Klicken Sie auf einen Knoten, um dort zu beginnen, und gehen Sie Schritt für Schritt vor, um die wartenden Knoten, ihre besten Kanten und das Wachsen des Baums zu sehen. Drücken Sie Abspielen, um dem Baum beim Wachsen zuzusehen, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Klicken Sie auf einen Knoten, um ihn zum Start zu machen: Der Baum wächst von dort aus. Die Zahl auf jeder Kante ist ihre Länge. Unter dem Graphen stehen die Knoten, die noch warten, jeweils mit der Länge ihrer besten Kante zum Baum, die gestrichelt gezeichnet ist. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Klicken Sie auf einen Knoten, um ihn zum Start zu machen: Der Baum wächst von dort aus.
- Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen.
- Beobachten Sie die wartenden Knoten unter dem Graphen, jeweils mit ihrer besten Kante zum Baum. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.
So funktioniert der Prim-Algorithmus
Beginnen Sie mit einem Baum aus einem Knoten. Jeder Knoten außerhalb des Baums merkt sich seine kürzeste Kante zum Baum, falls er eine hat. Nehmen Sie immer wieder den Knoten mit der kürzesten Kante, fügen Sie ihn und diese Kante zum Baum hinzu und prüfen Sie seine Kanten: Ist eine davon kürzer als die bisher beste Kante eines Nachbarn, wird sie dessen beste Kante. Wenn alle Knoten dazugekommen sind, hat der Baum eine Kante weniger, als es Knoten gibt, und seine Gesamtlänge ist so klein wie möglich.
Prim und Dijkstra
Der Prim- und der Dijkstra-Algorithmus sehen fast gleich aus: Beide lassen ein Gebiet von einem Start aus wachsen und halten die wartenden Knoten in einer Prioritätswarteschlange. Der Unterschied ist die Zahl in der Warteschlange. Dijkstra speichert für jeden Knoten den ganzen Abstand vom Start, Prim nur die Länge seiner einen besten Kante zum Baum. Daher baut Dijkstra einen Baum kürzester Wege und Prim einen Baum mit der kleinsten Gesamtlänge, und die beiden Bäume sind oft verschieden.
Häufig gestellte Fragen
Was ist der Prim-Algorithmus?
Ein gieriger Algorithmus, der einen minimalen Spannbaum eines gewichteten Graphen baut, indem er einen Baum von einem Startknoten aus wachsen lässt und immer die kürzeste Kante hinzufügt, die den Baum mit einem Knoten außerhalb verbindet.
Spielt der Startknoten eine Rolle?
Nur für die Reihenfolge: Von jedem Start aus endet der Prim-Algorithmus mit einem Spannbaum derselben kleinsten Gesamtlänge. Haben manche Kanten gleiche Längen, kann der Baum selbst anders aussehen.
Wer hat den Prim-Algorithmus erfunden?
Vojtěch Jarník beschrieb ihn als Erster, 1930. Robert Prim entdeckte ihn 1957 wieder und Edsger Dijkstra 1959, darum heißt er auch Jarník-Algorithmus oder Prim–Jarník-Algorithmus.
Wie schnell ist der Prim-Algorithmus?
Mit einem binären Heap wächst der Aufwand mit E log V, bei V Knoten und E Kanten. Mit einem einfachen Array statt eines Heaps braucht er etwa V² Schritte, was besser für dichte Graphen ist, in denen fast jedes Knotenpaar verbunden ist.
Wird mein Graph irgendwohin gesendet?
Nein. Der Graph wird in Ihrem Browser erzeugt und der Baum dort aufgebaut, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor