Minimaler Spannbaum mit Kruskal
Fügen Sie die günstigsten Kanten ohne Zyklen hinzu
Minimaler Spannbaum mit Kruskal ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was ein MST ist
Ein minimaler Spannbaum verbindet jeden Knoten mit dem geringstmöglichen Gesamtgewicht und enthält keine Zyklen. Stellen Sie sich vor, Sie verkabeln eine Stadt zu den geringstmöglichen Kosten. 🌲
Kruskals Kernidee
Kruskals Algorithmus ist konsequent gierig: Fügen Sie immer die günstigste Kante hinzu, die keinen Zyklus erzeugt, bis der gesamte Graph verbunden ist.
Schritt eins: Kanten sortieren
Sortieren Sie zunächst alle Kanten nach ihrem Gewicht, beginnend mit dem kleinsten. Die gierige Bevorzugung günstiger Kanten sorgt dafür, dass die endgültige Summe minimal ist.
edges.sort() # (weight, u, v)Warum DSU perfekt passt
Das Hinzufügen einer Kante erzeugt genau dann einen Zyklus, wenn ihre beiden Endpunkte bereits verbunden sind. DSU beantwortet diesen Zusammenhangstest nahezu in konstanter Zeit. 🤝
Die sortierten Kanten durchlaufen
Durchlaufen Sie die Kanten vom kleinsten bis zum größten Gewicht. Prüfen Sie bei jeder Kante, ob ihre beiden Endpunkte in der DSU bereits dieselbe Wurzel haben.
for w, u, v in edges:
ru, rv = find(u), find(v)Akzeptieren oder ablehnen
Unterscheiden sich die Wurzeln, verbindet die Kante zwei getrennte Teile. Akzeptieren Sie sie und vereinigen Sie die Teile. Stimmen die Wurzeln überein, überspringen Sie die Kante, um einen Zyklus zu vermeiden.
if ru != rv:
union(u, v)
total += wWissen, wann Sie stoppen müssen
Ein Spannbaum mit n Knoten hat genau n minus 1 Kanten. Sobald Sie diese Anzahl akzeptiert haben, können Sie vorzeitig stoppen.
Nichtzusammenhang erkennen
Wenn Sie alle Kanten verarbeitet haben, aber weniger als n minus 1 akzeptiert wurden, ist der Graph nicht zusammenhängend und es gibt keinen Spannbaum.
Die Laufzeit
Das Sortieren dominiert die Laufzeit, daher läuft Kruskals Algorithmus in O(E log E). Die DSU-Operationen sind so günstig, dass sie zur Gesamtlaufzeit kaum etwas beitragen.
Warum der gierige Ansatz korrekt ist
Die Schnitteigenschaft garantiert, dass die leichteste Kante über einen beliebigen Schnitt hinweg sicher hinzugefügt werden kann. Genau deshalb führt die Auswahl der günstigsten Kante zuerst nie in die Irre.
Wann Sie Kruskal verwenden sollten
Kruskals Algorithmus eignet sich besonders für dünn besetzte Graphen, die als Kantenliste gegeben sind – das Format, das Wettbewerbsaufgaben meist direkt liefern. ⚡
Kurztest
Entscheiden Sie, woran Kruskals Algorithmus erkennt, dass eine Kante abgelehnt werden muss.
Zusammenfassung
Sie haben Kruskals MST erstellt: Kanten sortieren, die günstigste Kante hinzufügen, die über DSU zwei Komponenten verbindet, und bei n minus 1 Kanten stoppen. 🎉
Häufig gestellte Fragen
Ist die Lektion „Minimaler Spannbaum mit Kruskal“ kostenlos?
Ja — der vollständige Text von „Minimaler Spannbaum mit Kruskal“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Minimaler Spannbaum mit Kruskal“?
Fügen Sie die günstigsten Kanten ohne Zyklen hinzu Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Minimaler Spannbaum mit Kruskal“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- DSU mit Pfadkompression
- Vereinigung nach Rang und Komponenten
- Minimaler Spannbaum mit Kruskal
- Prims MST mit einem Heap