Kruskal's Algorithm

Purpose

Kruskal's algorithm builds a minimum-spanning tree (MST) for a weighted and undirected graphs in the fastest way by using the weights.

Step-by-Step

  1. Sort all edges in a non-decreasing weight order.
  2. Start with an area where each vertex is its own component.
  3. For each edge in sorted order:
      a) if its endpoints are in different components, add the edge
      b) add them together
  4. Stop after N(number of nodes)-1 edges have been chosen.
Animated demonstration of Kruskal's algorithm
Edges are added from lightest to heaviest without creating cycles.

Read a full proof of optimality on the Kruskal’s algorithm Wikipedia page.