Kruskal's algorithm

An algorithm that builds a minimum spanning tree by sorting all edges by weight and adding each one unless it would create a cycle.

In more detail

Union-find answers "are these two vertices already connected?" in near-constant time, so sorting dominates the cost at O(E log E). It builds a forest of pieces that merge until V minus one edges connect everything. It suits sparse graphs given as edge lists.

Related terms

Taught in

References