Minimum Spanning Trees (MST)

Prim’s Algorithm

Prim’s Algorithm is a greedy algorithm that constructs a minimum spanning tree for a weighted undirected graph. It grows the MST by repeatedly choosing the minimum weight edge that connects a new vertex to the set of vertices already included.

Algorithm Steps

  1. Initialize the MST with a single starting vertex.
  2. Find the edge of smallest weight that connects the growing MST to a vertex not in the MST yet.
  3. Add this edge and the new vertex to the MST.
  4. Repeat until all vertices are included.

Diagram

Diagram illustrating Prim's Algorithm

For more details, check out Wikipedia: Prim’s Algorithm .