Kruskal’s algorithm

Algorithm that iteratively adds edges to a Minimum Spanning Tree (MST) being built, considering edges in the order of their weights, from smallest to largest. Our only exception is that edges that create a cycle when added to the current set of edges already in the MST should be skipped.

Algorithm summary:

  1. Initially, all vertices are placed in Disjoint Sets.
  2. The algorithm then selects the smallest edge in the graph and determines if the vertices connected by this edge are in the same set.
    1. If the vertices are in the same set, we move on to the next smallest edge (repeats step 2).
    2. If they are not in the same set, then that edge is added to the MST, and the vertices’ sets are unioned. This process continues from step 2 until all vertices are within the same disjoint set. #evergreen