# Prim’s algorithm

Prim's algorithm is a greedy algorithm as it  finds the global optimum answer from collecting locally optimum choices.It finds the minimum spanning tree and works for weighted,connected and undirected graph.Minimum spanning tree is a graph is edge weighted graph whose weight is smaller than any other spanning tree.A minimum spanning tree is obtained by combining all local optimal choices to a global one.

Technique

• Put   as the weight at all vertices of the graph.
• Write null as the parent of each vertex.
• Pick any vertex from the graph.
• Mark it and replace the distance from  ∞  to 0.
• Look for adjacent vertices of marked vertex.
• Replace   by given weights from the marked vertex to other vertices.
• Replace parent null by marked vertex name.
• Choose minimum weight edge from the marked vertex.
• Mark edge and another vertex .
• Look for the adjacent vertices.
• If edge weight is smaller then replace the value as well by the parent.
• Now,look for all  edges from previous and newly marked vertex.
• Choose the unvisited  vertex which is at minimum edge weight  from marked vertices.(Do not look again at  marked vertices).
• Repeat the process till optimum solution is reached.
• Minimum spanning tree is obtained as a result.

Example

Consider graph in Fig 1.

• Initially,put   followed by null and separated by comma at all vertices of graph.(Fig 2)
•    is the weight and null is the parent

• Choose any vertex from the graph.
• Say T is chosen.
• Mark T and replace weight  by 0.(Fig 3)
• Add T to the set i.e resulting sequence.

• Look for adjacent vertices of T.
• R,S,W are the adjacent vertices.
• Replace weights of R,S,W by 12,4,6 respectively  they are the distances from T.
• Replace parent of all adjacent vertices by T.(Fig 4)

• Choose the  edge from T which has minimum weight.
• Edge(T,S) is the shortest i.e 4(compared to 12 and 6).
• So mark the edge as well the vertex S.(Fig 5).
• Add S to the set.

• Look for adjacent neighbors of S.
• P,R,W are the adjacent vertices.
• Replace value at P by 13 and parent by S, as 13 is the edge weight from S to P.
• Compare the edge weight betweenEdge(S, R )and  Edge(T, R).
• S to R is 3 and T to R is 12.3 is smaller than 12.
• So,replace 12 by  3 and T by S.
• Compare weights between  Edge (S , W) and Edge (T ,W).
• S to W is 1 and T to W is 6.
• 1 is smaller so replace 6,T by 1,S.(Fig 6)

• Look for minimum edge  from T and S respectively.
• 1 is minimum value(Edge(S,W) ).
• Mark edge(S,W) ,vertex W and add them to the set.(Fig 7)

• Do not look for visited vertices again.
• Look for edges of T,S,W.
• 3 is minimum edge value.
• Mark edge and vertex R.
• Add R to the set.
• Look for unmarked adjacent vertices of R.
• P is the  unmarked vertex adjacent to R.
• Replace 13 by 5 and S by R as 5 is smaller than 13.(Fig 8)

• The next minimum value from edges of T,S,W,R is 5.
• Mark 5 and P.
• Add P to the set.(Fig 9)
• Replace value at Q by 2 and parent by P.(Fig 10)
• Mark 2 and vertex Q.
• Add Q to the set.(Fig 11)

Minimum spanning tree is obtained and shown in Fig 12 and cost of minimum spanning tree is obtained by adding weights of all edges i.e.

2+5+3+4+1 = 15

Rate this post