Minimum Spanning Tree - Kruskal's Algorithm
What is Minimum Spanning Tree (MST)? A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected and weighted graph. Thus MST is a tree . MST connects all the vertices/nodes of the graph together. MST does not contain any cycles . MST finds minimum edge weight . MST contains ( V-1) edges , where V is the number of vertices/nodes in the graph. No. of Spanning Trees possible for a graph (caution: Here I am not talking about Minimum Spanning Tree, but Spanning Tree in general): [ |E|C|V-1| ] - [no. of cycles] ( here C is Combination of pnc) Kruskal's Algorithm uses a Disjoint Set Data Structure to find Minimum Spanning Tree. Kruskal's Algorithm is a greedy algorithm. Kruskal's Algorithm 1. for each node perform makeSet() operation of disjoint set 2. sort each edge of the graph in non-decreasing order by weight 3. for each edge (u,v): 4. if findSet(u) != findSet(v)...