# 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. 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. Fig 2
• Now,mark Edge(S,W) with weight 1.
• Mark vertices S and W also.(Fig 3) Fig 3

• Next min weight edge is 2.
• Mark Edge(Q,P) and vertex P.(Fig 4) Fig 4

• The next min value in the graph is 3.
• Mark Edge(R,S).(Fig 5) 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) 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 Fig 7
Rate this post

## Comments

So empty here ... leave a comment!
Sidebar