- Aktuell
- Im Baum
- Neben dem Baum
- Bisher beste Kante
- Würde einen Kreis schließen
Minimaler Spannbaum
Sie wollen jede Stadt mit Kabel verbinden, jedes Haus mit Wasserleitungen oder jeden Computer in einem Netzwerk, mit so wenig Material wie möglich. Die Antwort ist ein minimaler Spannbaum: die Kanten, die alle Knoten mit der kleinsten Gesamtlänge verbinden. Wählen Sie den Kruskal- oder den Prim-Algorithmus und gehen Sie Schritt für Schritt vor, um den Baum wachsen zu sehen, jedes Mal um die kürzeste erlaubte Kante. 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. Wählen Sie den Algorithmus: Kruskal probiert die Kanten von der kürzesten bis zur längsten, Prim lässt einen Baum vom Start aus wachsen; klicken Sie auf einen Knoten, um ihn zum Start für Prim zu machen. Die Zahl auf jeder Kante ist ihre Länge. Unter dem Graphen steht die Liste der noch zu prüfenden Kanten oder die wartenden Knoten mit der Länge ihrer besten Kante zum Baum. 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
- Wählen Sie den Kruskal- oder den Prim-Algorithmus. Bei Prim klicken Sie auf einen Knoten, um ihn zum Start zu machen.
- 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, wie die Kanten in den Baum kommen und die Gesamtlänge wächst. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.
Kruskal-Algorithmus
Sortieren Sie alle Kanten von der kürzesten bis zur längsten und prüfen Sie sie in dieser Reihenfolge. Verbindet eine Kante zwei Teile, die noch nicht verbunden sind, kommt sie in den Baum. Sind ihre beiden Enden schon über den Baum verbunden, würde sie einen Kreis schließen, also wird sie übersprungen. Schluss ist, wenn der Baum eine Kante weniger hat, als es Knoten gibt. Um schnell zu erkennen, ob zwei Knoten schon verbunden sind, verwaltet der Kruskal-Algorithmus die Teile in einer Union-Find-Struktur.
Prim-Algorithmus
Beginnen Sie mit einem Baum aus einem Knoten. Jeder Knoten außerhalb des Baums merkt sich seine kürzeste Kante zum Baum. Fügen Sie immer wieder den Knoten mit der kürzesten Kante hinzu, zusammen mit dieser Kante, und prüfen Sie seine Kanten: Eine davon kann einem Nachbarn einen kürzeren Weg in den Baum geben. Der Prim-Algorithmus ähnelt dem Dijkstra-Algorithmus, vergleicht aber einzelne Kanten, nicht ganze Abstände vom Start. Beide Algorithmen enden immer mit derselben Gesamtlänge.
Häufig gestellte Fragen
Was ist ein minimaler Spannbaum?
In einem zusammenhängenden Graphen, dessen Kanten Längen haben, ist ein Spannbaum eine Menge von Kanten, die alle Knoten ohne Kreis verbindet; bei n Knoten hat er immer n − 1 Kanten. Ein minimaler Spannbaum ist ein Spannbaum mit möglichst kleiner Gesamtlänge.
Was ist der Unterschied zwischen dem Kruskal- und dem Prim-Algorithmus?
Der Kruskal-Algorithmus betrachtet die Kanten des ganzen Graphen von der kürzesten bis zur längsten und fügt getrennte Teile zu einem Baum zusammen. Der Prim-Algorithmus lässt einen einzigen Baum von einem Start aus wachsen und fügt immer die kürzeste Kante hinzu, die aus ihm herausführt. Beide sind gierig und finden einen Baum mit derselben Gesamtlänge; Kruskal eignet sich für dünne Graphen, Prim für dichte.
Ist der minimale Spannbaum eindeutig?
Wenn alle Kantenlängen verschieden sind, ja. Sind manche Längen gleich, kann es mehrere Bäume mit derselben kleinsten Gesamtlänge geben, und die Algorithmen wählen je nachdem, wie sie Gleichstände auflösen, vielleicht verschiedene.
Ist ein minimaler Spannbaum dasselbe wie kürzeste Wege?
Nein. Der minimale Spannbaum hält die Gesamtlänge aller Kanten klein, aber der Weg zwischen zwei Knoten im Baum kann viel länger sein als ihr kürzester Weg. Für kürzeste Wege nehmen Sie den Dijkstra-Algorithmus.
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