Skip to main content

Prim's Algorithm for MST

Properties

  • For Undirected graph

image

Implementation

  1. 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.

  1. Eager Implementation -

Only min weight edge with exactly one endpoint is added

Data Structure Used - Indexed Priority Queue, with decreaseKey API to decrease priority

image

image

image

image

image

image

image

image

image

image

Applications

  1. Euclidean MST

  2. Clustering (single-link clustering algorithm)

  3. Dendograms of cancers in humans