Kruskal-Algorithmus
Kanten sortieren, die kürzeste nehmen, nie einen Kreis schließen. Der Kruskal-Algorithmus ist vielleicht der einfachste gierige Algorithmus überhaupt, und doch findet er immer den günstigsten Weg, alle Knoten eines Graphen zu verbinden.
Die Idee
Ein minimaler Spannbaum verbindet alle Knoten eines gewichteten Graphen mit der kleinstmöglichen Gesamtlänge der Kanten. Der Kruskal-Algorithmus lässt keinen Baum von einem Start aus wachsen. Er betrachtet den ganzen Graphen auf einmal, beginnt mit jedem Knoten als eigenem Teil und verbindet Teile immer wieder über die kürzeste verfügbare Kante, bis nur noch ein Teil übrig ist.
Schritt für Schritt
Sortieren Sie die Kanten von der kürzesten bis zur längsten. Prüfen Sie sie in dieser Reihenfolge. Liegen die beiden Enden einer Kante in verschiedenen Teilen, fügen Sie sie zum Baum hinzu: Die beiden Teile werden eins. Liegen beide Enden schon im selben Teil, würde die Kante einen Kreis schließen, also wird sie übersprungen. Bei n Knoten ist der Baum nach n − 1 Kanten fertig, und die übrigen Kanten müssen gar nicht mehr betrachtet werden.
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. Kruskal nimmt A–B, dann B–C, das C an das Teil A–B anschließt. Als Nächstes kommt A–C, aber A und C liegen schon in einem Teil, also würde sie den Kreis A–B–C schließen und wird übersprungen. C–D schließt D an, und jetzt bilden alle vier Knoten einen Baum mit drei Kanten und der Gesamtlänge 7. B–D, die längste Kante, wird nicht einmal geprüft.
Union-Find
Die einzige schwierige Frage des Kruskal-Algorithmus lautet: Liegen diese beiden Knoten schon im selben Teil? Eine Union-Find-Struktur beantwortet sie. Jedes Teil ist ein kleiner Baum aus Verweisen, die auf einen Vertreter zeigen. Find folgt den Verweisen bis zum Vertreter; Union hängt einen Vertreter unter den anderen. Pfadkompression, die jeden besuchten Knoten direkt auf den Vertreter zeigen lässt, und Vereinigung nach Größe halten die Verweisketten so kurz, dass jede Frage fast konstante Zeit dauert.
Geschichte und Aufwand
Joseph Kruskal veröffentlichte den Algorithmus 1956 in einem kurzen Artikel in den Proceedings of the American Mathematical Society. Das Sortieren der Kanten ist der langsamste Teil, also wächst der Aufwand mit E log E, bei E Kanten. Sind die Kanten schon sortiert oder sind ihre Längen kleine ganze Zahlen, ist er fast linear.
Selbst ausprobieren
Öffnen Sie die App und drücken Sie Schritt. Die noch zu prüfenden Kanten stehen unter dem Graphen, die kürzeste zuerst. Jede Kante, die zwei Teile verbindet, wird grün; jede Kante, die einen Kreis schließen würde, wird rot gestrichelt. Sehen Sie zu, wie mehrere kleine Teile in verschiedenen Bereichen des Graphen wachsen und verschmelzen, und achten Sie darauf, dass die letzten Kanten oft nie geprüft werden.
Häufig gestellte Fragen
Warum sortiert der Kruskal-Algorithmus die Kanten?
Damit jede Kante, die er hinzufügt, die kürzeste ist, die noch zwei Teile verbindet. Diese gierige Wahl ist wegen der Schnitteigenschaft immer sicher, und jede übersprungene Kante ist die längste auf dem Kreis, den sie schließen würde, also wird sie nie gebraucht.
Was ist eine Disjoint-Set-Struktur?
Ein anderer Name für Union-Find: eine Struktur, die eine Sammlung getrennter Mengen verwaltet, hier die Teile des wachsenden Waldes, und schnell sagen kann, zu welcher Menge ein Element gehört, und zwei Mengen vereinigen kann.
Funktioniert der Kruskal-Algorithmus auf einem nicht zusammenhängenden Graphen?
Ja. Er endet einfach mit einem Baum für jedes zusammenhängende Stück des Graphen, einem minimalen Spannwald, denn keine Kante kann Stücke verbinden, die nicht zusammenhängen.
Wird der Kruskal-Algorithmus auch für anderes genutzt?
Hält man ihn früh an, bevor die letzten Teile verschmelzen, teilt er die Knoten in Cluster ein: Das ist Single-Linkage-Clustering. Lässt man ihn auf einem Gitter mit zufälligen Kantenlängen laufen, erzeugt er ein Labyrinth.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Kruskal-Algorithmus ausprobieren