GraphalgorithmenIntermediate
Kruskals MST-Algorithmus
Greedy-Algorithmus, der einen minimalen Spannbaum aufbaut, indem Kanten in Reihenfolge steigenden Gewichts hinzugefugt werden, unter Verwendung von Union-Find zur Vermeidung von Zyklen. Effizient fur dunn besetzte Graphen mit Zeitkomplexitat O(E log E). Anwendungen umfassen Netzwerkdesign, Clustering, Approximationsalgorithmen und Verstandnis von Greedy-Korrektheitsbeweisen.
#graph#minimum-spanning-tree#greedy#union-find
Complexity Analysis
Time (Average)
O(E log E)Expected case performance
Space
O(V)Memory requirements
Time (Best)
O(E log E)Best case performance
Time (Worst)
O(E log E)Worst case performance
đź“š CLRS Reference
Introduction to Algorithms•Chapter 23•Section 23.2
Loading...
Implementation