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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
Spannbaum: Teilgraph, der alle Knoten enthält + ein Baum ist (zusammenhängend + zyklenfrei +
V-1Kanten). Minimaler Spannbaum (MST): Spannbaum mit minimalem Gesamtgewicht der Kanten.
Bei V Knoten und Spannbaum:
V - 1 KantenWenn du eine Kante hinzufügst → ein Zyklus entsteht. Wenn du eine Kante entfernst → Graph zerfällt in zwei Komponenten.
MST ist nur definiert für zusammenhängende, ungerichtete, gewichtete Graphen. Bei gerichteten Graphen heißt das Konzept "Arboreszenz" und nutzt andere Algorithmen (Edmonds).
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).
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 | 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: 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.
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.
Graph mit 5 Knoten + 7 Kanten:
Kruskal:
MST: {C-D, A-C, B-C, D-E}, Gewicht = 1+2+3+4 = 10.
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.
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.
Ein Graph mit 5 Knoten + 7 Kanten. Beide Algorithmen finden denselben MST mit Gewicht 10.
Sieh:
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
6 Aufgaben zu MST-Eigenschaften, Prim, Kruskal, Komplexität.
Klausurfragen mit Lösungen (6)
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.
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).
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
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.
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
Zuordnungen:
Erklärung: MST-Algorithmen-Familie. Prim (Knoten-orientiert), Kruskal (Kanten-orientiert), Borůvka (parallel), Dijkstra ist für SPT, nicht MST.
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
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
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
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!
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.
Lösungen pro Lücke:
Erklärung: MST-Vokabular. V−1 Kanten, Kruskal vs. Prim, Außen-Kante bei Prim, beide Greedy.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Standard-Kruskal-Workflow. Sortieren → Union-Find init → Iteration → Zyklen-Check → Union → Stopp bei V-1.
Typ: Reihenfolge