Motivation
Lektion 2 von 9 im Kurs Prims Algorithmus - Graphenalgorithmen von Coddy.
Während Kruskal alle Kanten global sortiert und Union-Find verwendet, behält Prim einen einzelnen wachsenden Baum bei und greift wiederholt nach dem nächstgelegenen äußeren Knoten.
Warum Prim lernen?
- Dichte Graphen: Prim ist mit den richtigen Strukturen effizient, wenn es viele Kanten gibt.
- Schnitt-Eigenschaft: Es ist eine praktische Veranschaulichung dafür, warum die günstigste Kante, die den aktuellen Baum verlässt, immer sicher hinzugefügt werden kann.
- Zwei Sichtweisen auf ein Problem: Der Vergleich von Prim und Kruskal vertieft Ihr Verständnis von minimalen Spannbäumen.
Da alle MSTs eines Graphen die gleichen Kantengewichte teilen, melden Prim und Kruskal immer das gleiche Gesamtgewicht.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
