- Aktuell
- Im Baum
- Würde einen Kreis schließen
Kruskal-Algorithmus
Der Kruskal-Algorithmus baut einen minimalen Spannbaum, also die günstigste Menge von Kanten, die alle Knoten verbindet, auf die einfachste denkbare Art: Er nimmt die Kanten von der kürzesten bis zur längsten und behält jede, außer sie würde einen Kreis schließen. Gehen Sie Schritt für Schritt vor, um zu sehen, wie getrennte Teile wachsen und zu einem Baum verschmelzen, und welche Kanten übersprungen werden. 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. Die Zahl auf jeder Kante ist ihre Länge. Unter dem Graphen stehen die noch zu prüfenden Kanten, von der kürzesten bis zur längsten; eine Kante, deren Enden schon verbunden sind, würde einen Kreis schließen und ist rot gestrichelt. 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
- 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. Die noch zu prüfenden Kanten stehen unter dem Graphen, die kürzeste zuerst.
- Achten Sie auf die rot gestrichelten Kanten: Sie würden einen Kreis schließen. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.
So funktioniert der Kruskal-Algorithmus
Sortieren Sie alle Kanten von der kürzesten bis zur längsten. Zu Beginn ist jeder Knoten ein eigenes Teil. Prüfen Sie die Kanten der Reihe nach: Verbindet eine Kante zwei verschiedene Teile, kommt sie in den Baum, und die beiden Teile werden eins; liegen ihre beiden Enden schon im selben Teil, würde sie einen Kreis schließen, also wird sie übersprungen. Schluss ist, wenn alles ein Teil ist. Das ist nach einer Kante weniger, als es Knoten gibt, der Fall, oft lange bevor die letzte Kante geprüft wird.
Union-Find
Bei jeder Kante muss der Kruskal-Algorithmus fragen, ob ihre beiden Enden schon verbunden sind. Eine Union-Find-Struktur beantwortet das schnell: Jedes Teil hat einen Vertreterknoten, Find folgt den Verweisen bis zu ihm, und Union hängt einen Vertreter an den anderen. Mit zwei einfachen Tricks, Pfadkompression und Vereinigung nach Größe, dauert jede Frage fast konstante Zeit, also ist das Sortieren der Kanten der langsamste Teil, mit einem Aufwand, der mit E log E wächst.
Häufig gestellte Fragen
Was ist der Kruskal-Algorithmus?
Ein gieriger Algorithmus, der einen minimalen Spannbaum baut, indem er alle Kanten von der kürzesten bis zur längsten sortiert und jede Kante hinzufügt, die mit den schon gewählten Kanten keinen Kreis schließt.
Wie erkennt der Kruskal-Algorithmus einen Kreis?
Eine Kante schließt genau dann einen Kreis, wenn ihre beiden Enden schon über gewählte Kanten verbunden sind. Eine Union-Find-Struktur hält fest, welche Knoten verbunden sind, und beantwortet diese Frage fast sofort.
Warum funktioniert der Kruskal-Algorithmus?
Wegen der Kreiseigenschaft: Die längste Kante eines Kreises wird für einen minimalen Spannbaum nie gebraucht. Jede Kante, die Kruskal überspringt, ist die längste auf dem Kreis, den sie schließen würde, denn alle Kanten vor ihr waren kürzer oder gleich lang.
Wann nehme ich Kruskal statt Prim?
Der Kruskal-Algorithmus ist einfach und auf dünnen Graphen schnell, und er arbeitet direkt mit einer einfachen Kantenliste. Der Prim-Algorithmus eignet sich für dichte Graphen und für Graphen, die als Adjazenzlisten gespeichert sind. Beide finden einen Baum mit derselben Gesamtlänge.
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