Prim's Algorithm for MST
Properties
- For Undirected graph
Implementation
- Lazy Implementation -
An edge that is absolute (i.e. cannot be added because it will create a cycle in the MST) is left in the priority queue.
- Eager Implementation -
Only min weight edge with exactly one endpoint is added
Data Structure Used - Indexed Priority Queue, with decreaseKey API to decrease priority
Applications
-
Euclidean MST
-
Clustering (single-link clustering algorithm)
-
Dendograms of cancers in humans