Prim's MST Algorithm

Prim's MST Algorithm is an algorithm is an algorithm for finding the Minimum Spanning Tree of a graph. It is a Greedy Algorithm.

Time Complexity:

Prim's algorithm concept

  1. Start with an empty set of vertices . This will come to form a single tree.
  2. Start the algorithm from any vertex of the graph.
  3. Separate the chosen nodes from unvisited nodes with a Cut.
  4. Expand greedily across "safe" / Light edges until we have a full Spanning Tree

Prim's algorithm visual example

  1. We start at an arbitrary vertex, and separate it from the rest with a Cut.
    Pasted image 20240422010001.png

  2. We then expand along a Light Edge.
    Pasted image 20240422010050.png

  3. And again expand along a light edge. In this case either or could work, but we chose .
    Pasted image 20240422010109.png

  4. Continue until you have a full Spanning Tree.