What is Prim's Algorithm?

History of Prim’s Algorithm

The algorithm was discovered in 1930 by mathematician vojtech jarnik and later   independently by computer scientist Robert C. prim in 1957.

 Definition of Prim’s Algorithm

• Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted in-directed graph.

• The algorithm continuously increases the size of a tree starting with a single vertex until it spans all the vertices.   

• Graph must be connected and no cycle exists.

• It is similar to Dijkstra algorithm.

Pseudo code of  Prim’s Algorithm

A= ø

 for each v Є V

          KEY[v] = ∞

         PARENT = null

  KEY[r] = 0

 Q=V

 for each v Є Adj[u]:

While  Q! ≠ ø

       u= -MIN(Q) by KEY value

       Q=Q -u

if  PARANT(u) !=null:

A=AU(u , PARANT(u))

If v Є Q and W( u , v ) < KEY[v]:

         PARENT[v]=u

          KEY[v]=w

        return A

Time Complexity of Prim's Algorithm

Prim’s algorithm runs in O(V*V) = O(|V|²)

Applications of Prim’s Algorithm  

• Connect all computers in a computer science building using least amount of cable.

• Another useful application of MST would be finding airline routes. 

• The vertices of the graph would represent cities ,and the edges would represent routes between on the cities.