Kruskal's Algorithm

This page goes over Kruskal's Algorithm, a way to find the Minimum Spanning Tree of certain graphs. Below is the pseudocode for the algorithm and an example graph to facilitate understanding.

Definitions:

Steps of Algorithm (as taught in class):

  1. The method expects a list of edges in the graph with their edge weights.
  2. The algorithm undergoes a sorting algorithm that sorts the edges by their weights from smallest to largest.
  3. Initialize a helper data structure where each node is placed in a set, so every set contains exactly one node (a singleton set), and the sets do not overlap. Such sets are said to be disjoint. They help determine if two nodes are connected, in which case they will belong to the same set. In the example graph, there would be 9 singleton sets up to this step of the algorithm.
  4. Then, we process edges one by one using a while loop, until all edges are exhausted.
  5. For every loop, we pull off the next edge from the sorted list, which is the edge with the smallest weight so far. The edges will need to have data fields like the start node and end node.
  6. If the start and end nodes are in the same set, we know they are already connected in the spanning tree due to previous operations through some intermediate edges. For example, A and B are in the same set because A to E to B, which has the smallest sum of edge weights, was selected previously.
  7. If the start and end nodes are not yet in the same set, we will include the edge in our spanning tree, as it is guaranteed that this selection will constitute the spanning tree with the lowest sum of weights. Right after the addition of the edge, union the two sets that used to be disjoint in the helper data structure to show that the nodes are now connected and of the same set.

Complexity: O(Elog(V))

Additional Resources: