Prim’s algorithm

http://install4install.com

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

 

Example

 

Consider graph in Fig 1.

Screen Shot 2014-07-16 at 5.53.32 PM

Fig 1 : A weighted graph

 

Screen Shot 2014-07-16 at 5.57.22 PM

Fig 2

 

Screen Shot 2014-07-16 at 5.59.11 PM

Fig 3

 

Screen Shot 2014-07-16 at 6.01.50 PM

Fig 4

 

Screen Shot 2014-07-16 at 6.04.18 PM

Fig 5

 

Screen Shot 2014-07-16 at 6.07.02 PM

Fig 6

 

Screen Shot 2014-07-16 at 6.10.49 PM

Fig 7

 

Screen Shot 2014-07-16 at 6.13.52 PM

Fig 8

 

Screen Shot 2014-07-16 at 6.15.24 PM

Fig 9

Screen Shot 2014-07-16 at 6.16.20 PM

Fig 10

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

 

 

 



Short URL: http://tinyit.cc/ed088
Author: Cusp2207 on July 17, 2014
Category: Algorithms, Computer Science
Tags:

Leave a Reply

Last articles