Facebook

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.

Screen Shot 2014-07-16 at 5.53.32 PM
Fig 1 : A weighted graph

 

  • Initially,put   followed by null and separated by comma at all vertices of graph.(Fig 2)
  •    is the weight and null is the parent
Screen Shot 2014-07-16 at 5.57.22 PM
Fig 2

 

  • 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.
Screen Shot 2014-07-16 at 5.59.11 PM
Fig 3

 

  • 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)
Screen Shot 2014-07-16 at 6.01.50 PM
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.
Screen Shot 2014-07-16 at 6.04.18 PM
Fig 5

 

  • 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)
Screen Shot 2014-07-16 at 6.07.02 PM
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)
Screen Shot 2014-07-16 at 6.10.49 PM
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)
Screen Shot 2014-07-16 at 6.13.52 PM
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)
Screen Shot 2014-07-16 at 6.15.24 PM
Fig 9
  • Replace value at Q by 2 and parent by P.(Fig 10)
Screen Shot 2014-07-16 at 6.16.20 PM
Fig 10
  • Mark 2 and vertex Q.
  • Add Q to the set.(Fig 11)
Screen Shot 2014-07-16 at 6.17.26 PM
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

Screen Shot 2014-07-16 at 6.21.26 PM
Fig 12

 

 

 

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar