Mit Google fortfahren
Minimaler Spannbaum: Kruskal und Prim verstehen
Ein minimaler Spannbaum verbindet alle Knoten eines gewichteten, ungerichteten Graphen mit möglichst kleinem Gesamtgewicht. Er enthält keinen Kreis. Du kannst ihn zum Beispiel mit dem Kruskal- oder dem Prim-Algorithmus bestimmen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Woran erkennst du einen minimalen Spannbaum?
Ein Graph besteht aus Knoten und Kanten. Bei einem gewichteten Graphen trägt jede Kante eine Zahl, etwa eine Entfernung oder Kostenangabe.
Spannbaum
Ein Spannbaum enthält alle Knoten des Ausgangsgraphen, ist zusammenhängend und besitzt keinen Kreis. Ein Kreis ist ein geschlossener Weg, der zum Ausgangsknoten zurückführt.
Ein Spannbaum mit $n$ Knoten hat genau $n-1$ Kanten. Hat ein Graph beispielsweise fünf Knoten, benötigt jeder seiner Spannbäume vier Kanten.
Minimaler Spannbaum
Ein minimaler Spannbaum ist ein Spannbaum, dessen Kantengewichte zusammen die kleinstmögliche Summe ergeben. Die englische Abkürzung lautet MST für Minimum Spanning Tree.
Ein minimaler Spannbaum existiert nur, wenn der ungerichtete Graph zusammenhängend ist. Bei einem nicht zusammenhängenden Graphen entsteht stattdessen ein Spannwald aus mehreren Bäumen.
„Minimal“ bezieht sich auf die Summe der Kantengewichte – nicht auf die Anzahl der Kanten. Jeder Spannbaum desselben Graphen hat bereits gleich viele Kanten.
Wie arbeitet der Kruskal-Algorithmus?
Kruskal baut zunächst einen Wald aus einzelnen Knoten auf. Er prüft die Kanten vom kleinsten zum größten Gewicht und verbindet nach und nach verschiedene Komponenten.
- Sortiere alle Kanten aufsteigend nach ihrem Gewicht.
- Beginne mit allen Knoten, aber ohne Kanten.
- Prüfe die Kanten in der sortierten Reihenfolge.
- Nimm eine Kante auf, wenn dadurch kein Kreis entsteht.
- Beende das Verfahren, sobald $n-1$ Kanten aufgenommen wurden.
Eine Zusammenhangskomponente ist eine Gruppe von Knoten, die bereits durch Wege verbunden sind. Liegen die Endpunkte einer neuen Kante schon in derselben Komponente, würde die Kante einen Kreis schließen.
Gegeben ist ein ungerichteter Graph mit den Knoten A, B, C, D und E.
| Kante | Gewicht |
|---|---|
| BC | 1 |
| AB | 2 |
| DE | 2 |
| AC | 3 |
| BD | 4 |
| CD | 5 |
| CE | 6 |
Kruskal prüft die Kanten in dieser Reihenfolge:
- BC mit 1: aufnehmen. B und C werden verbunden.
- AB mit 2: aufnehmen. A kommt zur Komponente mit B und C.
- DE mit 2: aufnehmen. D und E bilden eine zweite Komponente.
- AC mit 3: verwerfen. A und C sind bereits über A–B–C verbunden; AC würde den Kreis A–B–C–A schließen.
- BD mit 4: aufnehmen. Die beiden bisherigen Komponenten werden verbunden.
Nun sind alle fünf Knoten durch vier Kanten verbunden. Das Gesamtgewicht beträgt $1+2+2+4=9$.
Bei gleich schweren Kanten kann die Prüfungsreihenfolge variieren. Dadurch können unterschiedliche minimale Spannbäume entstehen. Haben dagegen alle Kanten verschiedene Gewichte, ist der minimale Spannbaum eindeutig.
Warum führen günstige Kanten zum richtigen Ergebnis?
Kruskal handelt greedy: Der Algorithmus trifft jeweils eine dauerhaft gültige, möglichst günstige Entscheidung. Die Begründung dafür liefert die Schnitteigenschaft.
Schnitt
Ein Schnitt teilt die Knoten in zwei Gruppen. Eine Kante kreuzt den Schnitt, wenn ihre Endpunkte in verschiedenen Gruppen liegen. Der Schnitt ist mit den bereits gewählten Kanten verträglich, wenn keine von ihnen ihn kreuzt.
Unter den Kanten, die einen solchen verträglichen Schnitt kreuzen, ist eine Kante mit minimalem Gewicht eine sichere Wahl. Angenommen, ein minimaler Spannbaum enthält stattdessen eine teurere Kante über denselben Schnitt: Fügt man die leichtere Kante hinzu, entsteht ein Kreis. Entfernt man daraus die andere Schnittkante, bleibt der Graph ein Spannbaum und wird nicht teurer. So entsteht wieder ein minimaler Spannbaum.
Bei Kruskal bilden die bisherigen Komponenten die entscheidenden Gruppen. Die nächste zulässige Kante verbindet zwei dieser Komponenten mit dem kleinsten noch verfügbaren Gewicht.
Eine günstige Kante darf nicht allein wegen ihres Gewichts gewählt werden. Sie muss zwei verschiedene Komponenten verbinden und darf keinen Kreis schließen.
Wie wächst ein Spannbaum mit Prim?
Prim beginnt nicht mit einem Wald, sondern mit einem beliebigen Startknoten. Von dort wächst genau ein zusammenhängender Baum.
- Wähle einen Startknoten.
- Betrachte alle Kanten vom bisherigen Baum zu noch nicht aufgenommenen Knoten.
- Wähle darunter eine Kante mit kleinstem Gewicht.
- Füge die Kante und den neuen Knoten hinzu.
- Wiederhole dies, bis alle Knoten enthalten sind.
Prim startet im Beispielgraphen bei A:
- Von A führen AB mit 2 und AC mit 3 nach außen. Prim wählt AB.
- Vom Baum mit A und B führen unter anderem BC mit 1 und BD mit 4 nach außen. Prim wählt BC.
- Vom Baum mit A, B und C ist BD mit 4 die günstigste Verbindung zu einem neuen Knoten.
- Nun verbindet DE mit 2 den letzten Knoten E mit dem Baum.
Der Spannbaum enthält AB, BC, BD und DE. Sein Gesamtgewicht ist wieder $2+1+4+2=9$.
Der Startknoten darf beliebig gewählt werden. Bei Gewichtsgleichständen können verschiedene Entscheidungen zu verschiedenen, aber gleich teuren minimalen Spannbäumen führen.
Wie unterscheiden sich Kruskal, Prim und kürzeste Wege?
Kruskal und Prim lösen dasselbe Problem, treffen ihre Auswahl aber aus unterschiedlichen Mengen.
| Merkmal | Kruskal | Prim |
|---|---|---|
| Start | alle Knoten, keine Kanten | ein beliebiger Startknoten |
| Zwischenzustand | Wald aus mehreren Komponenten | ein zusammenhängender Baum |
| nächste Wahl | global günstigste kreisfreie Kante | günstigste Kante vom Baum zum Rest |
| typische Datenstruktur | Union-Find | Prioritätswarteschlange oder Heap |
Union-Find verwaltet die Komponenten bei Kruskal. Find prüft, ob zwei Knoten bereits zur gleichen Komponente gehören. Union vereinigt zwei Komponenten nach der Aufnahme einer Kante.
Ein minimaler Spannbaum ist kein kürzester Weg. Beim minimalen Spannbaum soll die gesamte Verbindung aller Knoten möglichst wenig kosten. Ein Kürzeste-Wege-Verfahren minimiert dagegen die Weglänge zwischen bestimmten Knoten oder von einem Startknoten zu anderen Knoten.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Kruskal lässt zunächst einen wachsen. Prim erweitert immer einen . Beide minimieren das .
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Minimaler Spannbaum
- Eigenschaften: alle Knoten verbunden, keine Kreise, kleinstes Gesamtgewicht
- Kruskal: Kanten sortieren, Komponenten verbinden, Kreise vermeiden
- Prim: Startknoten wählen, Baum über günstigste ausgehende Kanten erweitern
- Abgrenzung: Gesamtvernetzung statt kürzester Einzelweg
Abschluss-Check
Du bist fertig, wenn du bei jeder gewählten Kante zwei Fragen beantworten kannst: Verbindet sie die richtigen Teile des Graphen? Und: Warum ist keine zulässige günstigere Wahl nötig?