Minimum Spanning Tree Using Kruskal’s algorithm

Minimum Spanning Tree Using Kruskal’s algorithm

Given a weighted, undirected and connected graph. The task is to find the sum of weights of the edges of the Minimum Spanning Tree

Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

Spanning Tree – A tree that spans all the vertices of a connected and undirected graph .

Spanning Tree Properties

  • for graph G(V, E), it contains exact (V-1) edges
  • Remove (E-V+1) edges
  • Maximally acyclic – Means after adding an edge will be cycle
  • Minimally connected – means removable of an edge from spinning tree it will give more than one components
  • maximum possible spinning tree is V ^ (V-2)
Solution:
  • In Kruskal’s algorithm use disjoint set with find – union operation
  • its greedy
Algorithm
  1. Take all edges
  2. Sort edges in ascending order
  3. Iterate all edges one by one
    1. find disjoint set of source vertex of edge
    2. find disjoint set of destination vertex of edge
    3. if both sets are different then,
      1. add edge to output list
      2. union both sets
  4. return output list of edge

Video

Video

Latest Source Code:
Github: MinimumSpanningTreeKruskalAlgorithm.java


Output:

 Minimum Spanning Tree Edges: 
0 - 1 --> 2
1 - 2 --> 3
1 - 4 --> 5
0 - 3 --> 6
Author: Hrishikesh Mishra