Kruskal’s Algorithm in Data Structure

Kruskal’s Algorithm produces the disjoint set in the data structure. To maintain several disjoint sets of elements each set contains the vertices in a tree of the current forest. The operation to find set u returns the Q representation element from the set that contains u. Thus we can determine whether two vertices u and v belong to the same tree by testing whether find set (u) is equal to find set (v). The combining of the tree is accomplished by the union procedure.

Algorithm with the Explanation

1. A $ \gets \phi $
2. For each vertex V $ \epsilon $ V[G]
3. do MAKE_SET[u]
4. sort the edges of E into non-decreasing order of weight w.
5. For each edge (u,v) $ϵ$ E, taken in non-decreasing order
6. do if FIND_SET (u) $\neq $ FIND_SET (v)
7. then A $ \gets $ A $\cup $ {(u,v)}
8. UNION(u,v)
9. Return A

1. Lines 1-3 initialize, a set A to the empty set. So, that empty set and create [v]
2. Line 4 edges in the key are sorted in non-decreasing order by weight
3. In Lines 5-\7 the for loop checks for each edge (u,v) whether the endpoints (u,v) belong to the same tree if yes then the edge is discarded. Since the edge (u,v) cannot be added to the forest without creating a cycle. And if the two vertices belong to different trees the edges (u,v) are added to (A).
4. In line 8 the vertices of 2 different trees are merged in line(A).

Problem-Based on Kruskal’s Algorithm with Solution

Problem

Solution:

According to the algorithm, sort edges in ascending order to find the solution

(a,d) =1

(e,f) = 1

(c,e) = 2

(d,e) = 3

(c,d) = 4

(d,f) = 4

(a,c) = 7

(a,b) = 12

(b.c) = 14

Now first take the shortest edge (a,d) =1 and put in a set A ={(a,d)}

So, the solution will be

The next edge in order is (e,f) = 1 So, put in a set A ={(a,d), (e,f)}

So, the solution will be

The next edge in order is (c,e) = 2 So, put in a set A ={(a,d), (e,f), (c,e)}

So, the solution will be

The next edge in order is (d,e) = 3 So, put in a set A ={(a,d), (e,f), (c,e),(d,e)}

So, the solution will be

The next edge in order are (c,d) = 4, (d,f)=4, (a,c)=7 but we did not considered them as the tree will become a closed loop.

The next edge in order is (a,b) = 12 So, put in a set A ={(a,d), (e,f), (c,e),(e,d).(a,b)}

So, the solution of the problem is

Since all the vertices are traverse above solution is final as we will not consider the edge (b,c) as it again making a closed loop