Kruskal's Algorithm - Minimum Cost Spanning Tree Problem

"Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component)." - Wikipedia

1. MST_KRUSKAL(G, cost)
2.   A -> φ
3.   for each vertex v ∈ V[G]
4.     do MAKE-SET(v)
5.   sort the edges of E into non-decreasing order by weight
6.   for each edge (u,v) ∈ E taken in non-decreasing order by weight
7.     do if FIND-SET(u) ≠ FIND-SET(v)
8.       then A <- A ∪ { (u,v) }
9.         UNION(u,v)
10.  return A

MAKE-SET(x) -> creates a new set (tree) whose only
member is x (creates disjoint sets)

UNION(x,y) -> unites the dynamic sets that contain x & y, 
say Sx & Sy into a new set that is the union of these two sets 
Sx & Sy are assumed to be disjoint prior to this operation

FIND-SET(x) -> return a pointer to the representative of the set
containing x (here the root of the tree to which it belongs to)

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil