Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Minimale Spannbäume (MST), Prim & Kruskal
Du sollst alle Städte mit Glasfaser verbinden, möglichst billig. Welche Kabel-Strecken? Das ist das MST-Problem: in einem zusammenhängenden, gewichteten Graphen den billigsten Baum finden, der alle Knoten verbindet. Klausur-Klassiker in 11/17 WInf-Algo-Klausuren, zwei Algorithmen (Prim, Kruskal), beide greedy.
Die Idee in einem Satz
Spannbaum: Teilgraph, der alle Knoten enthält + ein Baum ist (zusammenhängend + zyklenfrei +
V-1Kanten). Minimaler Spannbaum (MST): Spannbaum mit minimalem Gesamtgewicht der Kanten.
Eigenschaften jedes Spannbaums
Bei V Knoten und Spannbaum:
- Genau
V - 1Kanten - Kein Zyklus
- Zusammenhängend (jeder Knoten erreichbar)
Wenn du eine Kante hinzufügst → ein Zyklus entsteht. Wenn du eine Kante entfernst → Graph zerfällt in zwei Komponenten.
Voraussetzung
MST ist nur definiert für zusammenhängende, ungerichtete, gewichtete Graphen. Bei gerichteten Graphen heißt das Konzept "Arboreszenz" und nutzt andere Algorithmen (Edmonds).
Kruskal-Algorithmus
Greedy auf Kanten. Iteriere durch alle Kanten in aufsteigender Gewicht-Reihenfolge und nimm jede, die KEINEN Zyklus schließt.
kruskal(graph):
mst = []
sort edges by weight ascending
init union-find with all nodes
for edge (u, v) in sorted edges:
if find(u) != find(v): # nicht im selben Cluster
mst.append(edge)
union(u, v)
if len(mst) == V - 1: break
return mst
Zyklen-Check: Union-Find-Datenstruktur, O(α(n)) ≈ O(1) pro Operation (Inverse Ackermann).
Komplexität: O(E log E) (dominiert von Sortierung).
Prim-Algorithmus
Greedy auf Knoten. Starte bei einem Knoten, erweitere den Baum schrittweise um die billigste Außen-Kante (Kante mit einem Endpunkt im Baum, einem außerhalb).
prim(graph, start):
mst = []
visited = {start}
pq = PriorityQueue of edges from start
while len(visited) < V:
(weight, u, v) = pq.extractMin()
if v in visited: continue
mst.append((u, v))
visited.add(v)
for each neighbor w of v:
if w not in visited:
pq.insert((weight(v, w), v, w))
return mst
Komplexität: O((V + E) log V) mit Binary Heap. Wie Dijkstra.
Prim vs. Kruskal
| Prim | Kruskal | |
|---|---|---|
| Strategie | Knoten-orientiert (wachsender Baum) | Kanten-orientiert (kleinste Kanten zuerst) |
| Datenstruktur | Priority Queue (Heap) | Union-Find + sortierte Kanten |
| Komplexität | O((V+E) log V) | O(E log E) |
| Besser für | dichte Graphen (E ≈ V²) | dünne Graphen (E ll V²) |
| Implementierung | wie Dijkstra | einfacher |
Beide finden das GLOBALE Optimum (MST ist eindeutig bei eindeutigen Kantengewichten).
Cut-Eigenschaft (Beweis-Werkzeug)
Cut-Eigenschaft: Für jeden Cut (Partition der Knoten in zwei nicht-leere Mengen) ist die billigste Kante, die den Cut kreuzt, in JEDEM MST enthalten.
Folgerung: Beide Algorithmen (Prim und Kruskal) addieren in jedem Schritt eine "sichere" Kante, eine, die in mindestens einem MST liegen MUSS.
MST ist nicht eindeutig
Bei mehreren Kanten mit gleichem Gewicht kann es mehrere MSTs geben, alle mit dem gleichen Gesamtgewicht. Klausur-Frage: "Ist der MST eindeutig?" → nur wenn alle Kantengewichte verschieden sind.
Beispiel
Graph mit 5 Knoten + 7 Kanten:
- A-B (4), A-C (2), B-C (3), B-D (5), C-D (1), C-E (6), D-E (4)
Kruskal:
- Sortiere: C-D (1), A-C (2), B-C (3), A-B (4), D-E (4), B-D (5), C-E (6)
- Nimm C-D (1) → mst
- Nimm A-C (2) → mst
- Nimm B-C (3) → mst
- A-B (4) → würde Zyklus → skip
- D-E (4) → mst (V-1=4 Kanten erreicht → fertig)
MST: {C-D, A-C, B-C, D-E}, Gewicht = 1+2+3+4 = 10.
Klausur-Faustregeln
1. MST hat V-1 Kanten, ist zyklenfrei + zusammenhängend.
2. Kruskal: sortiere Kanten, nimm in Reihenfolge wenn kein Zyklus. Union-Find für Zyklen-Check.
3. Prim: starte irgendwo, erweitere mit billigster Außen-Kante. Priority Queue.
4. Beide O(E log E) bzw. O(E log V). Bei dichten Graphen Prim mit Array O(V²).
5. Cut-Eigenschaft = Garantie für Greedy-Korrektheit.
Häufige Stolpersteine
1. Algorithmen verwechseln. Prim ist KNOTEN-zentriert (Baum wächst), Kruskal ist KANTEN-zentriert (alle Kanten sortiert).
2. Zyklen bei Kruskal übersehen. Ohne Union-Find prüfst du falsch. Naive Zyklen-Erkennung wäre O(V) pro Kante.
3. MST mit Shortest-Path-Tree verwechseln. MST = globales Minimum aller Kanten. SPT (z.B. von Dijkstra) = kürzeste Wege von einer Wurzel. Andere Bäume!
4. Eindeutigkeit annehmen. Bei gleichen Kantengewichten gibts mehrere MSTs.
5. Auf gerichteten Graphen anwenden. MST funktioniert nur auf UNGERICHTETEN Graphen. Gerichtete Variante = Edmonds-Algorithmus.
Interaktiv verstehen
Prim vs. Kruskal Side-by-Side
Ein Graph mit 5 Knoten + 7 Kanten. Beide Algorithmen finden denselben MST mit Gewicht 10.
Sieh:
- Welche Kante in welchem Schritt gewählt wird
- Warum die Wahl getroffen wird (Prim: billigste Außen-Kante, Kruskal: nächste sortierte Kante ohne Zyklus)
- Identisches Endergebnis trotz unterschiedlicher Strategien
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Praxis-Übung
Minimale Spannbäume, Praxis-Übung
6 Aufgaben zu MST-Eigenschaften, Prim, Kruskal, Komplexität.
Klausurfragen mit Lösungen (6)
- F1.Wie viele Kanten hat ein Spannbaum eines Graphen mit V Knoten?
Antwort: V−1
Erklärung: Spannbaum hat exakt V−1 Kanten. Jeder Baum mit V Knoten hat V−1 Kanten. Mehr → Zyklus. Weniger → nicht zusammenhängend.
- F2.Welche Daten-Struktur braucht Kruskal hauptsächlich für effiziente Zyklen-Erkennung?
Antwort: Union-Find (Disjoint-Set)
Erklärung: Union-Find erlaubt fast-konstante Zyklen-Checks: find(u) und find(v) sind im selben Set? Wenn ja → Zyklus. Operationen O(α(n)) ≈ O(1).
- F3.Prim ist Knoten-zentriert (Baum wächst), Kruskal ist Kanten-zentriert (Kanten sortiert).
Antwort: Wahr
Erklärung: RICHTIG. Prim wählt den nächsten KNOTEN für den wachsenden Baum (billigste Außen-Kante). Kruskal iteriert durch alle KANTEN sortiert und nimmt die zyklenfreien. Beide finden denselben MST.
Typ: Wahr/Falsch
- F4.Was ist die Komplexität von Kruskal?
Antwort: O(E log E)
Erklärung: O(E log E), dominiert durch Sortierung der Kanten. Union-Find-Operationen sind nahezu O(1). Bei E ≈ V² wird E log E = V² log V.
- F5.Welche Aussagen über MST sind RICHTIG?
Richtige Antworten: MST hat V−1 Kanten; Bei eindeutigen Kantengewichten ist der MST eindeutig; Prim und Kruskal finden denselben MST; Die Cut-Eigenschaft garantiert Greedy-Korrektheit
Erklärung: Richtig: V−1 Kanten, eindeutig bei verschiedenen Gewichten, Prim+Kruskal gleicher MST, Cut-Eigenschaft. Falsch: MST nur ungerichtet (gerichtet = Edmonds); Prim/Kruskal sind O(E log V) bzw. O(E log E), nicht V².
Typ: Multi-Select
- F6.Ordne Algorithmus der Hauptidee zu:
Zuordnungen:
- Prim → Wachsender Baum + billigste Außen-Kante (Priority Queue)
- Kruskal → Alle Kanten sortieren + Zyklen-Check via Union-Find
- Borůvka → Parallele Wahl: jeder Baum-Komponente nimmt billigste Außen-Kante
- Dijkstra → NICHT für MST! Kürzeste Wege von einem Start
Erklärung: MST-Algorithmen-Familie. Prim (Knoten-orientiert), Kruskal (Kanten-orientiert), Borůvka (parallel), Dijkstra ist für SPT, nicht MST.
Typ: Zuordnung
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Graph: A-B (4), A-C (2), B-C (3), B-D (5), C-D (1), C-E (6), D-E (4). Was ist das Gesamt-Gewicht des MST?
Antwort: 10
Erklärung: Kruskal-Reihenfolge: C-D (1), A-C (2), B-C (3), D-E (4) → MST. Σ = 1+2+3+4 = 10. A-B(4) würde Zyklus (A-C-B existiert), also skip.
Typ: Zahlen-Eingabe
- F2.Der MST eines Graphen mit allen verschiedenen Kantengewichten ist eindeutig.
Antwort: Wahr
Erklärung: RICHTIG. Wenn alle Kantengewichte verschieden sind, ist der MST eindeutig, jeder Greedy-Schritt hat genau eine billigste Wahl. Bei gleichen Gewichten kann es mehrere MSTs gleicher Kosten geben.
Typ: Wahr/Falsch
- F3.Bei einem dichten Graphen (E ≈ V²): welcher Algorithmus ist asymptotisch besser?
Antwort: Prim mit Array, O(V²)
Erklärung: Prim mit Array hat O(V²), das ist besser als O(V² log V) für dichte Graphen. Bei dünnen Graphen ist Heap-Prim oder Kruskal schneller. Anpassung an Graph-Dichte zählt!
- F4.Was sagt die Cut-Eigenschaft?
Antwort: Für jeden Cut ist die billigste den Cut kreuzende Kante in jedem MST
Erklärung: Cut-Eigenschaft: Für jede Partition (Cut) der Knoten ist die billigste Kante über den Cut in JEDEM MST drin. Garantiert die Korrektheit von Greedy-Algorithmen wie Prim und Kruskal.
- F5.Ein MST hat {{1}} Kanten bei V Knoten. {{2}} sortiert alle Kanten und nutzt Union-Find für Zyklen-Check. {{3}} wächst einen Baum vom Start aus mit billigster {{4}}-Kante. Beide sind {{5}}-Algorithmen.
Lösungen pro Lücke:
- {{1}}: V-1 / V−1 / V−1 Kanten
- {{2}}: Kruskal
- {{3}}: Prim
- {{4}}: Außen / Aussen / äußere
- {{5}}: Greedy / greedy
Erklärung: MST-Vokabular. V−1 Kanten, Kruskal vs. Prim, Außen-Kante bei Prim, beide Greedy.
Typ: Lückentext
- F6.Sortiere: Kruskal-Algorithmus.
Richtige Reihenfolge:
- Sortiere alle Kanten aufsteigend nach Gewicht
- Initialisiere Union-Find mit allen Knoten
- Iteriere durch sortierte Kanten
- Wenn find(u) ≠ find(v): nimm Kante in MST
- union(u, v): füge Komponenten zusammen
- Stoppe bei V-1 Kanten im MST
Erklärung: Standard-Kruskal-Workflow. Sortieren → Union-Find init → Iteration → Zyklen-Check → Union → Stopp bei V-1.
Typ: Reihenfolge
