Prim's algorithm


In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.


The algorithm may informally be described as performing the following steps:

  1. Select any vertex to be the first of the tree T.
  2. Consider which edge connects vertices in T to vertices outside T. Pick the edge with the minimum weight (if there are more than one, then choose any). Add this edge and vertex to T.
  3. Repeat step 2 until T contains every vertex of the graph.