Prims MST mit einem Heap
Erweitern Sie den Baum ausgehend von einem Knoten
Prims MST mit einem Heap ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Ein anderer Weg zum MST
Prims Algorithmus findet ebenfalls einen minimalen Spannbaum, erweitert aber einen zusammenhängenden Bereich nach außen, statt zuerst alle Kanten zu sortieren. 🌱
Von einem Knoten aus wachsen
Wählen Sie einen beliebigen Startknoten und markieren Sie ihn als besucht. Der Baum beginnt mit einem einzelnen Knoten und wächst Kante für Kante.
visited = [False] * nDie Idee der Grenze
Betrachten Sie in jedem Schritt alle Kanten, die vom Baum nach außen führen. Prims Algorithmus wählt immer die günstigste dieser Randkanten.
Ein Heap wählt das Minimum
Ein Min-Heap macht das Finden der günstigsten Randkante schnell. Fügen Sie Kandidatenkanten hinzu und entfernen Sie in jeder Runde das kleinste Kantengewicht.
import heapq
heap = [(0, start)]Die günstigste Kante entfernen
Entfernen Sie den kleinsten Eintrag aus dem Heap. Er liefert Ihnen das Gewicht und den nächsten Knoten, der am günstigsten an den wachsenden Baum angehängt werden kann.
w, u = heapq.heappop(heap)Veraltete Einträge überspringen
Ein Knoten kann mehr als einmal im Heap liegen. Wenn Sie einen Eintrag entfernen, dessen Knoten bereits besucht wurde, ignorieren Sie ihn einfach und entfernen Sie den nächsten.
if visited[u]:
continueHinzufügen und erweitern
Markieren Sie den entfernten Knoten als besucht und addieren Sie sein Gewicht zur Gesamtsumme. Fügen Sie anschließend jede ausgehende Kante in den Heap ein, damit sie später verarbeitet werden kann.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Bis zur Vollständigkeit wiederholen
Entfernen und erweitern Sie Einträge so lange, bis jeder Knoten besucht wurde. Dann ist die aufgelaufene Summe das Gewicht des minimalen Spannbaums.
Die Laufzeit
Jede Kante kann einmal eingefügt und einmal entfernt werden. Daher läuft Prims Algorithmus mit Heap in O(E log V) und ist damit mit Kruskals Algorithmus vergleichbar.
Prims Algorithmus und Kruskals Algorithmus
Verwenden Sie Prim bei dichten Graphen mit einer Adjazenzliste und Kruskal, wenn bereits eine einfache Kantenliste vorliegt. Beide liefern dasselbe MST-Gewicht.
Es sieht wie Dijkstra aus
Die Heap-Schleife ähnelt Dijkstra, aber Sie vergleichen die reinen Kantengewichte und nicht die Wegdistanzen. Wenn Sie dieses Muster erkennen, sparen Sie beim Programmieren Zeit. ⚡
Kurztest
Rufen Sie sich ins Gedächtnis, wie Prim in jeder Runde die nächste Kante auswählt.
Zusammenfassung
Sie haben mit Prim einen MST erstellt: an einem beliebigen Knoten starten, mit einem Min-Heap die günstigste Randkante hinzufügen und veraltete Besuche überspringen. Gute Arbeit! 🎉
Häufig gestellte Fragen
Ist die Lektion „Prims MST mit einem Heap“ kostenlos?
Ja — der vollständige Text von „Prims MST mit einem Heap“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Prims MST mit einem Heap“?
Erweitern Sie den Baum ausgehend von einem Knoten Du übst Coding Interview Prep 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep 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 4 von 4.
Wie lange dauert die Lektion „Prims MST mit einem Heap“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-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