Kruskal's algorithm

Lore & Background

Kruskal's algorithm operates by first creating a forest of single-vertex trees, one for each vertex in the graph. It then sorts all graph edges by weight and iterates through them in ascending order. For each edge, it tests whether adding it to the current forest would create a cycle; if not, the edge is added, combining two trees into one. The algorithm uses a disjoint-set data structure to efficiently detect cycles and manage the forest components. The algorithm's running time is dominated by the sorting step, achieving O(E log E) time (or equivalently O(E log V) for graphs with no isolated vertices). After sorting, the disjoint-set operations take amortized time O(E α(V)), where α is the extremely slowly growing inverse Ackermann function. In cases where edges are already sorted or can be sorted in linear time using integer sorting, the total time becomes O(E α(V)). A parallel variant called Filter-Kruskal has been described by Osipov et al., which partitions edges similarly to quicksort and filters out edges connecting vertices of the same tree to reduce sorting costs. This variant lends itself better to parallelization as sorting, filtering, and partitioning can be performed in parallel by distributing edges between processors.

Reader's Guide

Kruskal's algorithm is a foundational method in graph theory and computer science for constructing minimum spanning trees and forests. Its significance lies in its simplicity and efficiency, using a greedy approach that always selects the lowest-weight edge that does not create a cycle. The algorithm's reliance on sorting and disjoint-set data structures makes it a classic example of how data structures can optimize algorithmic performance. Its correctness is proven by induction, showing that the set of chosen edges is always contained within some minimum spanning tree. The algorithm is inherently sequential and hard to parallelize, but variants like Filter-Kruskal have been developed to improve parallel performance. Kruskal's algorithm remains widely taught and used in network design, clustering, and other applications requiring optimal connectivity with minimal total edge weight.

Did You Know?

• The algorithm's running time is dominated by the time to sort all graph edges by weight.
• Filter-Kruskal, a parallel variant, partitions edges similarly to quicksort and filters out edges connecting vertices of the same tree.
• The disjoint-set data structure operations in Kruskal's algorithm take amortized time O(E α(V)), where α is the inverse Ackermann function.