Minimale Spannbäume
1926 sollte Otakar Borůvka das Stromnetz im Süden Mährens so günstig wie möglich planen. Seine Frage, wie man jeden Ort mit der kleinsten Gesamtlänge an Leitung verbindet, ist das Problem des minimalen Spannbaums, und es hat einige der einfachsten und elegantesten Lösungen der ganzen Informatik.
Das Problem
Nehmen Sie einen zusammenhängenden Graphen, dessen Kanten Längen oder Kosten haben. Ein Spannbaum ist eine Menge von Kanten, die alle Knoten verbindet und keinen Kreis enthält; bei n Knoten hat er immer genau n − 1 Kanten, denn jede Kante bindet einen weiteren Knoten an. Unter allen Spannbäumen hat ein minimaler Spannbaum die kleinste Gesamtlänge. Ein Graph kann enorm viele Spannbäume haben, aber man muss nicht alle ausprobieren.
Warum gierig funktioniert
Teilen Sie die Knoten beliebig in zwei Gruppen. Die kürzeste Kante zwischen den Gruppen gehört immer zu einem minimalen Spannbaum: Nutzte ein Baum stattdessen eine längere Kante zwischen den Gruppen, würde der Tausch gegen die kürzere dieselben Knoten günstiger verbinden. Das ist die Schnitteigenschaft. Die Kehrseite ist die Kreiseigenschaft: Die längste Kante eines Kreises wird nie gebraucht. Beide Algorithmen unten wenden einfach immer wieder diese Regeln an.
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. Der Kruskal-Algorithmus nimmt A–B, dann B–C, überspringt dann A–C, weil A und C schon verbunden sind und sie einen Kreis schließen würde, und nimmt dann C–D. Der Baum hat drei Kanten für vier Knoten, also ist er fertig, mit Gesamtlänge 7, und B–D wird nicht einmal betrachtet. Der Prim-Algorithmus fügt von A aus zuerst B über A–B hinzu; die Kante B–C (2) von B schlägt A–C (3) als Weg zu C, also kommt C über B–C dazu; die Kante C–D (4) von C schlägt B–D (5), also kommt D über C–D dazu. Derselbe Baum, dieselbe 7.
Kruskal, Prim und Borůvka
Der Kruskal-Algorithmus, 1956 von Joseph Kruskal veröffentlicht, sortiert die Kanten und überspringt mit einer Union-Find-Struktur Kanten innerhalb eines Teils, also wächst sein Aufwand mit E log E. Der Prim-Algorithmus wurde zuerst 1930 von Vojtěch Jarník beschrieben und 1957 von Robert Prim und 1959 von Edsger Dijkstra wiederentdeckt; mit einem binären Heap wächst sein Aufwand mit E log V, mit einem einfachen Array mit V², was gut für dichte Graphen ist. Borůvkas Algorithmus von 1926 lässt jedes Teil gleichzeitig seine kürzeste ausgehende Kante nehmen, was zu Parallelrechnern passt.
Anwendungen
Mit minimalen Spannbäumen plant man günstige Netze aus Kabeln, Rohren und Straßen. Sie gruppieren Daten in Cluster: Entfernt man die längsten Kanten des Baums, sind die übrigen Teile die Cluster. Sie liefern für das Problem des Handlungsreisenden schnell eine Rundreise, die höchstens doppelt so lang ist wie die beste, wenn die Abstände die Dreiecksungleichung erfüllen. Und der Kruskal- oder Prim-Algorithmus auf einem Gitter mit zufälligen Kantenlängen ist eine klassische Art, ein Labyrinth zu erzeugen.
Selbst ausprobieren
Öffnen Sie die App, wählen Sie Kruskal oder Prim und drücken Sie Schritt. Bei Kruskal stehen die noch zu prüfenden Kanten unter dem Graphen, von der kürzesten bis zur längsten; Kanten, die einen Kreis schließen würden, sind rot gestrichelt. Bei Prim stehen dort die wartenden Knoten mit der Länge ihrer besten Kante, die gestrichelt gezeichnet ist. Lassen Sie beide auf demselben Graphen laufen und vergleichen Sie: Die Reihenfolge ist anders, aber die Gesamtlänge ist immer gleich.
Häufig gestellte Fragen
Wie viele Kanten hat ein Spannbaum?
Genau eine weniger, als es Knoten gibt. Weniger Kanten könnten nicht alle Knoten verbinden, und eine mehr würde immer einen Kreis erzeugen.
Was ist schneller, Kruskal oder Prim?
Der Kruskal-Algorithmus, der die Kanten sortiert, ist meist einfacher und auf dünnen Graphen mit wenigen Kanten schnell. Der Prim-Algorithmus mit einem Heap ist auf dichten Graphen gut, und mit einem einfachen Array braucht er etwa V² Schritte, egal wie viele Kanten es gibt.
Was ist Union-Find?
Eine Datenstruktur, die festhält, welche Knoten im selben Teil liegen. Sie beantwortet „Sind diese beiden verbunden?“ und vereinigt zwei Teile fast sofort, und genau das braucht der Kruskal-Algorithmus für jede Kante.
Gibt es minimale Spannbäume auch für gerichtete Graphen?
Nicht direkt. Für Graphen mit Einbahnkanten ist das entsprechende Problem die minimale aufspannende Arboreszenz, die der Chu–Liu/Edmonds-Algorithmus löst.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Einen minimalen Spannbaum bauen