Kruskal Algorithm for Minimum Spanning tree

Function Kruskal (G)

The above Procedure subalgorithm finds the minimum spanning tree of the graph ‘G’. The graph ‘G’ is the undirected connected weighted graph. In this procedure we are using disjoint set data sturcture Union-Find.

Step 1 Initially M is empty

set M ¬ {f} R set is empty

step 2 Loop, for each vertex create a set

Repeat through step 4 For Vi ¬ V1, V2 .... V R Vi Î V

call to Create–Set (Vi)

Step 3 Loop, set E is sorted in increasing order by weight

for each (( Vi, Vj) from the sorted list)

if (Find (Vi) ¹ Find (Vj)) then

Vi and Vj are in different trees

set M ¬ { call to Addedge (Vi, Vj)} R add edge to M

call to Union ( Vi, Vj)

Step 4 Return M, at the point of call

return (M).