Algorithmes de grapheIntermediate
Kruskal's MST Algorithm
Greedy algorithm that builds a minimum spanning tree by adding edges in order of increasing weight, using union-find to avoid cycles. Efficient for sparse graphs with time complexity O(E log E). Applications include network design, clustering, approximation algorithms, and understanding greedy correctness proofs.
#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