Facebook

Kruskal’s Algorithm

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

  • Mark the minimum weight edge in the graph and mark the respective vertices.
  • Now,mark the next minimum value in the graph.
  • If there are two or more edges with same weight then select any edge at one time and then select others one by one.
  • We need to mark edges according to the increasing weight of edges of different vertices.
  • Do not mark any edge on the graph which makes a cycle.
  • Keep on repeating the process till MST is obtained.

Example

Consider connected weighted graph in Fig 1.

Screen Shot 2014-07-18 at 12.25.40 PM
Fig 1 : A Graph

 

  • The minimum edge weight on the graph is 1.Edge(Q,R) and Edge (S,W) have same weight i.e 1.
  • Choose any edge between them.
  • Say we mark Edge(Q,R).(Fig 2)
  • Mark vertices Q and R also.
Screen Shot 2014-07-18 at 12.27.33 PM
Fig 2
  • Now,mark Edge(S,W) with weight 1.
  • Mark vertices S and W also.(Fig 3)
Screen Shot 2014-07-18 at 12.29.54 PM
Fig 3

 

  • Next min weight edge is 2.
  • Mark Edge(Q,P) and vertex P.(Fig 4)
Screen Shot 2014-07-18 at 12.55.52 PM
Fig 4

 

  • The next min value in the graph is 3.
  • Mark Edge(R,S).(Fig 5)
Screen Shot 2014-07-18 at 12.34.01 PM
Fig 5

 

  • The next min value is 4.
  • Choose any edge between Edge(Q,T) or Edge(S,T).
  • Say we mark Edge(S,T) with weight 4.
  • The next value to be marked is 4 but if we will mark Edge(Q,T) a cycle SRQTS will be formed.
  • So,do not mark this edge.
  • We do  not mark Edge(P,R) with weight 5,Edge(T,W) with weight 6,Edge(P,S) with weight 13 for the same reason.(Cycle formation).
  • Now,mark Edge(W,X) with weight 14 and mark vertex X.(Fig 6)
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
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