Kruskal's algorithm: greedy method for minimum spanning trees

Step-by-step procedure

The algorithm proceeds as follows:

1. Collect all edges and sort them by nondecreasing weight.
2. Start with an empty forest: each vertex is a separate component.
3. Examine edges in sorted order. For each edge, add it if it connects two different components; otherwise skip it (it would form a cycle).
4. Continue until you have a single tree spanning all vertices (or all edges have been considered, yielding a minimum spanning forest).

This simple loop is usually implemented together with a disjoint-set (union–find) data structure to test whether two vertices lie in the same component and to merge components when an edge is chosen.

Data structures and complexity

The dominant cost is sorting the edges. With E edges and V vertices, sorting takes O(E log E) time, often expressed as O(E log V) since E ≤ V^2. Union–find operations (find and union) can be done in virtually constant amortized time using path compression and union by rank, so the overall running time is roughly O(E log E) in typical analyses.

Correctness and properties

Correctness is established by standard MST principles such as the cut and cycle properties: the minimum-weight edge crossing any cut belongs to some MST, and the heaviest edge on any cycle is never required in every MST. Kruskal's greedy choice of the smallest available safe edge respects these properties and yields an MST. When edge weights are distinct the MST is unique; equal weights can produce multiple MSTs.

Variants, implementation tips, and use cases

• Use efficient sorting or bucket/radix methods when weights are integers in a limited range.
• Union–find optimizations (path compression and union by rank/size) are essential for performance on large graphs.
• Kruskal's algorithm is especially convenient when the input is already an edge list or when the graph is sparse; Prim's algorithm can be preferable for dense graphs with suitable priority queues.

Applications include network design (telecommunications, road and utility networks), clustering (single-linkage hierarchical clustering), and some image segmentation methods. For further background and formal proofs consult standard algorithm texts and introductory resources on greedy algorithms, minimum spanning trees, and graph models.

History. The method was described by Joseph B. Kruskal in 1956 and remains one of the fundamental algorithms studied in algorithm courses and used in practice.