Kruskal’s Algorithm

For a Minimum Spanning Tree.
All edges are sorted in increasing order.

Essentially the idea is to take the “cheapest” edge you can as long as that edge does not form a cycle.

1. Sort all edges by weight (ascending)
2. Initialize a forest
3. Iterate over edges from smallest to largest
   1. If an edge connects two different trees, add it to the MST and merge those trees
4. Stop when you’ve added n-1 edges or run out of edges

Note

You want to use a Disjoint Union Set / Union-find to make step 3 fast