Minimaler Spannbaum und Kruskal in Python

Problem

Das billigste Netz

Die Lieferfirma hat sechs Büros in der Stadt und will sie mit Glasfaser verbinden. Jedes Büro muss jedes andere erreichen, direkt oder über andere Büros. Graben ist teuer: Jedes mögliche Kabel hat einen Preis in Tausend Euro (Tsd. €).

offices = ["Zentrum", "Nord", "Süd", "Ost", "West", "Flughafen"]
cables = [
    ("Zentrum", "Nord", 4),
    ("Zentrum", "Süd", 6),
    ("Zentrum", "Ost", 8),
    ("Zentrum", "West", 5),
    ("Nord", "Ost", 9),
    ("Nord", "West", 3),
    ("Süd", "West", 7),
    ("Süd", "Flughafen", 11),
    ("Ost", "Flughafen", 2),
]

Alle neun Kabel zu verlegen kostet 55 Tsd. €. Aber du brauchst nicht alle. Wenn drei Büros im Ring verbunden sind, ist ein Kabel des Rings überflüssig: Entferne es, und alles ist weiter verbunden. Das billigste Netz hat gar keinen Zyklus. Ein zusammenhängender Graph ohne Zyklus ist ein Baum, und ein Baum mit V Knoten hat genau V − 1 Kanten: hier 5 Kabel.

Welche fünf? Du suchst den Baum, der alle Büros zum niedrigsten Gesamtpreis aufspannt. Das ist ein minimaler Spannbaum (MST).

Die Idee

Das billigste Kabel, das keinen Zyklus schließt

Der Algorithmus von Kruskal (Joseph Kruskal, 1956):

Sortiere die Kabel nach Preis, das billigste zuerst.
Für jedes Kabel: Wenn seine beiden Enden noch nicht verbunden sind, verlege es. Wenn sie über verlegte Kabel schon verbunden sind, würde das Kabel einen Zyklus schließen: überspringe es.
Halte an, sobald es V − 1 Kabel sind.

Am Anfang ist jedes Büro eine eigene Gruppe. Jedes verlegte Kabel verschmilzt zwei Gruppen zu einer. Die Frage „sind die beiden Enden verbunden“ ist genau die Frage „sind sie in einer Gruppe“, und dafür gibt es eine Struktur: Union-Find. union(a, b) verschmilzt die Gruppen und gibt false zurück, wenn a und b schon in einer Gruppe sind. Eine Prüfung statt einer Suche über die Karte.

Sieh es dir an

Kruskal von innen

Die Klasse UnionFind ist dieselbe wie in der Lektion zu Union-Find, unverändert. Ein Kabel ist ein Tupel (Büro, Büro, Preis), und index macht aus dem Namen eines Büros eine Zahl, weil Union-Find mit Zahlen arbeitet.

def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if not groups.union(index[a], index[b]):
            continue  # ein Zyklus
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 1:
            break
    return tree

sorted mit key=lambda c: c[2] sortiert nach dem dritten Element, dem Preis, und ist stabil.

total = 0
for a, b, cost in kruskal(offices, cables):
    print(f"{a} – {b}: {cost} Tsd. €")
    total += cost
print(f"Gesamt: {total} Tsd. €")

Ost – Flughafen: 2 Tsd. €
Nord – West: 3 Tsd. €
Zentrum – Nord: 4 Tsd. €
Zentrum – Süd: 6 Tsd. €
Zentrum – Ost: 8 Tsd. €
Gesamt: 23 Tsd. €

def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if not groups.union(index[a], index[b]):
            continue  # ein Zyklus
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 1:
            break
    return tree

Schritt für Schritt, in Worten

Sechs Büros, neun mögliche Kabel, jedes mit einem Preis in Tausend Euro. Das Netz muss alle Büros so billig wie möglich verbinden. Rechts werden die Kabel nach Preis sortiert: Kruskal schaut sie vom billigsten an. Am Anfang ist jedes Büro eine eigene Gruppe.
Ost – Flughafen, 2: verschiedene Gruppen. Das Kabel wird verlegt, und union verschmilzt die beiden Gruppen zu einer (gleiche Farbe).
Nord – West, 3: wieder verschiedene Gruppen. Eine zweite, getrennte Gruppe entsteht: Kruskal baut mehrere Stücke gleichzeitig, nicht einen Baum, der wächst.
Zentrum – Nord, 4: Das Büro Zentrum kommt in die Gruppe von Nord und West.
Zentrum – West, 5: Beide Enden sind schon in einer Gruppe, über Nord. Dieses Kabel würde einen Zyklus schließen: union gibt false zurück, und das Kabel wird abgelehnt.
Zentrum – Süd, 6: Das Büro Süd ist allein, also wird das Kabel verlegt.
Süd – West, 7: Süd und West sind schon über Zentrum verbunden. Abgelehnt.
Zentrum – Ost, 8: das billigste Kabel zwischen den beiden Gruppen. Es verschmilzt sie, und jetzt sind es fünf Kabel: sechs Büros, fünf Kabel, alles ist verbunden.
Die Schleife endet: Nord – Ost und Süd – Flughafen werden gar nicht angeschaut. Gesamt 23 Tausend €, gegenüber 55 für alle neun Kabel.

Zwei Gruppen wachsen getrennt: die blaue (Ost, Flughafen) und die grüne, die von Nord und West ausgeht. Das Kabel Zentrum – Ost ist das billigste zwischen ihnen und verschmilzt sie. Die Kabel Nord – Ost (9) und Süd – Flughafen (11) werden nie angeschaut.

Probier es aus

Sag die Ausgabe voraus

Die Autobahn zum Flughafen erweist sich als Problem: Das Kabel Ost – Flughafen kostet jetzt 12. Was kostet das neue Netz?

changed = cables[:-1] + [("Ost", "Flughafen", 12)]
total = sum(cost for _, _, cost in kruskal(offices, changed))
print(f"Gesamt: {total} Tsd. €")

Antwort

Gesamt: 33 Tsd. €

Gesamt: 30 Tsd. €

Gesamt: 32 Tsd. €

Probier es aus

Ergänze

tree.append((a, b, cost))
if len(tree) == :
    break

Die Idee

Warum gierig hier richtig ist

Kruskal ist ein gieriger Algorithmus: In jedem Schritt nimmt er die beste Möglichkeit im Moment (das billigste Kabel, das passt) und geht nie zurück. Gierig täuscht oft: siehe wann gierig funktioniert und wann es scheitert. Hier funktioniert es, und der Grund ist die Schnitteigenschaft.

Teile die Büros auf beliebige Weise in zwei Teile, etwa die Gruppe Ost und alles andere. Die Kabel, die zwischen den beiden Teilen verlaufen, sind der Schnitt. Das billigste Kabel im Schnitt ist im minimalen Baum. Warum? Der Baum braucht mindestens ein Kabel über den Schnitt, sonst sind die beiden Teile nicht verbunden. Ist dieses Kabel teurer, tausche es gegen das billigste: Das Netz bleibt verbunden, und der Preis sinkt.

Jedes Kabel, das Kruskal verlegt, ist das billigste im Schnitt zwischen der Gruppe eines seiner Enden und allem anderen: Alle billigeren Kabel sind schon vorbei und liegen innerhalb von Gruppen. Zentrum – Ost (8) ist das billigste von Zentrum – Ost, Nord – Ost (9) und Süd – Flughafen (11), den Kabeln zwischen den beiden Gruppen.

Probier es aus

Finde den Fehler

Ein Kollege hat entschieden, dass union unnötig ist, und fragt nur mit find, ob die beiden Enden in einer Gruppe sind:

def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if groups.find(index[a]) == groups.find(index[b]):
            continue
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 1:
            break
    return tree

total = 0
for a, b, cost in kruskal(offices, cables):
    print(f"{a} – {b}: {cost} Tsd. €")
    total += cost
print(f"Gesamt: {total} Tsd. €")

Ost – Flughafen: 2 Tsd. €
Nord – West: 3 Tsd. €
Zentrum – Nord: 4 Tsd. €
Zentrum – West: 5 Tsd. €
Zentrum – Süd: 6 Tsd. €
Gesamt: 20 Tsd. €

20 Tsd. € statt 23, aber Ost und Flughafen sind abgeschnitten, und Zentrum, Nord und West bilden einen Ring. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Was es kostet

Das Sortieren von E Kabeln kostet O(E log E). Danach ist jede Prüfung mit Union-Find fast O(1) (siehe die Lektion zu Union-Find). Insgesamt O(E log E): Das Sortieren ist der teure Teil.

Ohne Union-Find wird „sind sie verbunden“ mit der Tiefensuche über die bisher verlegten Kabel gefragt:

def connected(net, start, goal):
    stack = [start]
    seen = {start}
    while stack:
        office = stack.pop()
        if office == goal:
            return True
        for other in net[office]:
            if other not in seen:
                seen.add(other)
                stack.append(other)
    return False


def kruskal_slow(offices, cables):
    net = {office: [] for office in offices}
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if connected(net, a, b):
            continue
        net[a].append(b)
        net[b].append(a)
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 1:
            break
    return tree

Die Antwort ist dieselbe. Aber jede Suche kann die ganze Gruppe durchlaufen, O(V), und sie läuft für jedes Kabel: O(E · V).

Lass beide Versionen auf Büros in einem Gitter laufen: Jedes Büro kann mit seinem rechten und unteren Nachbarn verbunden werden, zu einem Preis von 1 bis 1000. Gezählt wird jeder Vergleich zweier Preise beim Sortieren, jeder Nachbar, den die Tiefensuche anschaut, und jeder Schritt zu einem Elternknoten in find.

Kruskal mit DFS: eine Suche über die verlegten Kabel O(n²)
Kruskal mit Union-Find O(n log n)

Algorithmus	n = 100	n = 1.000	n = 10.000	n = 100.000
Kruskal mit DFS: eine Suche über die verlegten Kabel	4.945	677.351	≈ 67.735.100	≈ 6.773.510.000
Kruskal mit Union-Find	1.460	23.827	321.171	3.884.598

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

def kruskal(offices, cables):
    index = {o: i for i, o in enumerate(offices)}
    groups = UnionFind(len(offices))
    tree = []
    for a, b, cost in sorted(cables, key=lambda c: c[2]):
        if not groups.union(index[a], index[b]):
            continue  # ein Zyklus
        tree.append((a, b, cost))
        if len(tree) == len(offices) - 1:
            break
    return tree

Bei 1000 Büros braucht die Tiefensuche 677.351 Schritte, Union-Find 23.827. Bei 100.000 Büros macht Union-Find 3.884.598, und die Tiefensuche würde Milliarden machen: Bench lässt sie nicht laufen, sondern schätzt sie aus der Kurve.

Die Idee

Nicht der kürzeste Weg

Im minimalen Baum ist der Weg von Süd zum Flughafen Süd – Zentrum – Ost – Flughafen: 6 + 8 + 2 = 16. Das direkte Kabel Süd – Flughafen kostet 11, ist aber nicht im Netz.

Ein minimaler Spannbaum spart am Gesamtpreis des Netzes. Über den Weg zwischen zwei Büros verspricht er nichts. Wenn der Preis die Verzögerung ist und du den schnellsten Weg zwischen zwei Büros willst, ist das ein anderes Problem: Dijkstra.

Genauer, für Neugierige

Prim ist der andere klassische Algorithmus für einen minimalen Spannbaum. Er beginnt bei einem Büro und fügt jedes Mal das billigste Kabel vom Baum zu einem Büro außerhalb hinzu. Die Warteschlange ist eine Prioritätswarteschlange wie bei Dijkstra, nur ist die Priorität der Preis des Kabels, nicht der Weg vom Start. Mit einem binären Heap ist es O(E log V). Kruskal ist einfacher, wenn die Kabel eine Liste sind, Prim, wenn der Graph über Nachbarn gegeben und dicht ist.

Haben einige Kabel denselben Preis, kann es mehrere minimale Bäume geben, alle mit demselben Gesamtpreis. Kruskal gibt einen davon zurück, je nach Reihenfolge der gleichen.

Wo noch: Strom- und Wassernetze, Straßen zwischen Dörfern, Leiterplatten. Wenn du Kruskal anhältst, bevor die Gruppen eine werden (etwa bei k Gruppen), bekommst du Clustering: Die Punkte einer Gruppe liegen nah beieinander, und die Gruppen liegen weit voneinander.

Übung

Ein Kabel liegt schon

Löse es in deinem Editor.

Ein altes Kabel. Zwischen Nord und Ost liegt schon ein Kabel: Es kostet nichts. Schreibe eine Methode, die auch die verlegten Kabel bekommt und findet, welche neuen hinzukommen. Gib die verlegten und die neuen Kabel und den Preis der neuen aus:

Schon verlegt: Nord – Ost
Ost – Flughafen: 2 Tsd. €
Nord – West: 3 Tsd. €
Zentrum – Nord: 4 Tsd. €
Zentrum – Süd: 6 Tsd. €
Neue Kabel: 15 Tsd. €

Tipp: Verschmilz vor der Schleife die Enden der verlegten Kabel in Union-Find. Halte an, sobald es eine Gruppe ist.

Weitere Aufgaben

Die abgelehnten. Gib auch die abgelehnten Kabel aus, jedes mit dem Grund: welchen Zyklus es schließen würde.
Zwei Netze. Die Firma will zwei getrennte Netze. Halte Kruskal an, wenn es zwei Gruppen sind. Welche Büros teilen sich ein Netz?
Unmöglich. Entferne jedes Kabel zum Flughafen. Was gibt Kruskal zurück? Woran erkennst du, dass das Netz nicht alle Büros verbindet?

Test

Teste dich

1. Ein Netz verbindet 6 Büros so billig wie möglich. Wie viele Kabel hat es?Das hängt von den Preisen ab65

2. Kruskal erreicht ein Kabel, dessen beide Enden schon in einer Gruppe sind. Was tut es?Es hält an: Das Netz ist fertigEs verlegt es, wenn es billiger ist als die bisherigenEs überspringt das Kabel: Es würde einen Zyklus schließen

3. Warum benutzt Kruskal Union-Find statt einer Suche (Tiefensuche) über die verlegten Kabel?Weil die Tiefensuche eine falsche Antwort gibtWeil Union-Find die Kabel sortiertDie Prüfung „sind sie verbunden“ kostet fast O(1) statt O(V)

4. Im minimalen Spannbaum führt der Weg von Süd zum Flughafen über Zentrum und Ost, 16 Tsd. €. Das direkte Kabel Süd – Flughafen kostet 11. Heißt das, der Baum ist falsch?Ja: Kruskal übersieht das Kabel für 11Ja: Es müssten 11 seinNein: Er minimiert den Gesamtpreis, nicht den Weg zwischen zwei Büros

Minimaler Spannbaum

Cookies