Time and Space Complexity
Lektion 7 von 9 im Kurs Kruskals Algorithmus - Graph-Algorithmen von Coddy.
Zeitkomplexität:
- Das Sortieren der E Kanten ist O(E log E); jede Union-Find-Operation ist mit Pfadkompression nahezu O(1), daher ist der klassische Kruskal-Algorithmus O(E log E). Die hier erstellte Min-Selection-Version ist O(E2), was für kleine Graphen in Ordnung ist.
Platzkomplexität:
- O(V) für das parent array (plus die Eingabekanten).
Zusammenfassung:
- Kruskal lässt einen MST wachsen, indem in jedem Schritt die günstigste kreisfreie Kante hinzugefügt wird, wobei Union-Find verwendet wird, um auf Zyklen zu prüfen.
- Alle MSTs haben das gleiche Gesamtgewicht, daher ist das Ergebnis eindeutig.
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.
Alle Lektionen in Kruskals Algorithmus - Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity