Kruskal's Algorithm

What it does

Finds the minimal spanning tree of a weighted, connected, undirected graph represented as a list of edges

Pseudocode

  1. Sorts the list of edges by weight
  2. Initializes a set of singleton sets which each contain one vertex of the graph
  3. Goes through the list of edges, if the edge connects vertices from different sets, combine the sets and add the edge to the MST

Example MST found using Kruskal's

Further readings

Wikipedia