Kruskal’s Algorithm

http://install4install.com

Kruskal’s algorithm is a greedy technique  used to find minimum spanning tree from the graph.It works on edges rather than on vertices in connected weighted graph.MST is obtained by finding global optimal choice.

Technique

Example

Consider connected weighted graph in Fig 1.

Screen Shot 2014-07-18 at 12.25.40 PM

Fig 1 : A Graph

 

Screen Shot 2014-07-18 at 12.27.33 PM

Fig 2

Screen Shot 2014-07-18 at 12.29.54 PM

Fig 3

 

Screen Shot 2014-07-18 at 12.55.52 PM

Fig 4

 

Screen Shot 2014-07-18 at 12.34.01 PM

Fig 5

 

Screen Shot 2014-07-18 at 12.35.15 PM

Fig 6

 

Minimum spanning tree is obtained as shown in Fig 7 and cost of minimum spanning tree is obtained by adding weights of all edges i.e 2+1+3+4+1+14=25

Screen Shot 2014-07-18 at 12.36.55 PM

Fig 7



Short URL: http://tinyit.cc/91e90b
Author: Cusp2207 on July 18, 2014
Category: Algorithms, Computer Science
Tags:

Leave a Reply

Last articles