Prim's Algorithm

A Greedy algorithm that grows an MST from a starting source vertex until it spans the entire graph:

  • Start with an empty minimum spanning tree $T = \{\}$.
  • Pick a vertex $v$ (at random) and add it to $T$.
  • Choose a vertex $u$ not in $T$, such that the edge weight from a vertex in $T$ to $u$ is the least among all such edges.
  • Add $u$ to $T$. 
  • Repeat until $(N – 1)$ edges were added.
Demo
Resources