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.
- 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.
Consider connected weighted graph in Fig 1.
- 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.
- Now,mark Edge(S,W) with weight 1.
- Mark vertices S and W also.(Fig 3)
- Next min weight edge is 2.
- Mark Edge(Q,P) and vertex P.(Fig 4)
- The next min value in the graph is 3.
- Mark Edge(R,S).(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)
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