Kruskal's algorithm

Kruskal's algorithm works on an undirected graph where each edge has a weight. It produces a minimum spanning forest: for a connected graph, this is a minimum spanning tree; for a disconnected graph, it gives one minimum spanning tree per connected component. The algorithm is greedy, repeatedly picking the lightest edge that does not create a cycle and adding it to the growing forest. To do this efficiently, it first sorts all edges by weight, then uses a disjoint-set data structure to quickly check whether an edge’s endpoints are already in the same tree. The overall running time is dominated by the sorting step, which takes O(E log E) time (or equivalently O(E log V) for graphs without isolated vertices). If the edges are already sorted or can be sorted in linear time (e.g., with counting sort or radix sort), the disjoint-set operations become the bottleneck, adding O(E α(E,V)) time, where α is the inverse Ackermann function.

The algorithm starts by creating a forest where each vertex is its own tree. It then sorts all edges by weight. Going through the edges from lightest to heaviest, for each edge it tests whether adding it would form a cycle. If not, the edge is added, merging two trees into one. When all edges have been processed, the resulting forest is a minimum spanning forest.

In pseudocode, using a disjoint-set data structure: function Kruskal(Graph G) is F := ∅ for each v in G.Vertices do MAKE-SET(v) for each {u, v} in G.Edges ordered by increasing weight({u, v}) do if FIND-SET(u) ≠ FIND-SET(v) then F := F ∪ { {u, v} } UNION(FIND-SET(u), FIND-SET(v)) return F

The proof of correctness has two parts. First, the algorithm always produces a spanning tree (or forest). It cannot create a cycle because edges that would form one are rejected. It cannot leave the graph disconnected, because the first edge that would join two separate components will eventually be added. Second, the spanning tree is minimal. This is shown by induction: at every step, the set of chosen edges F can be extended to some minimum spanning tree that also contains none of the edges already rejected. Initially, when F is empty, any minimum spanning tree works. When a new edge e is added, if it is already in that minimum spanning tree T, the property holds. If e is not in T, then adding e to T creates a cycle. That cycle must contain an edge f that is not in F and not e, and f belongs to T. Since f was not considered earlier, its weight is at least as large as e’s weight (otherwise the algorithm would have picked f first). Replacing f with e in T yields another spanning tree with total weight no greater than T’s, so the property continues to hold.

Joseph Kruskal first published the algorithm in 1956; it was rediscovered soon after by Loberman and Weinberger in 1957. Other algorithms for the same problem include Prim’s algorithm, Borůvka’s algorithm, and the reverse-delete algorithm.