Kruskals

Kruskal's algorithm, named after Joseph B. Kruskal who described it in 1956, is a greedy algorithm for finding a minimum spanning tree of a connected weighted graph. It can also produce a minimum spanning forest for disconnected graphs. The algorithm operates by considering edges in nondecreasing order of weight and adding an edge if it connects two previously disconnected components, thereby avoiding cycles.

The standard procedure is: sort all edges by weight, initialize a forest where each vertex is its own component, and for each edge in sorted order, add the edge if it joins two different components. This process uses a disjoint-set union (union-find) data structure to efficiently test whether two vertices belong to the same component and to merge components when an edge is accepted. Path compression and union by rank are common optimizations.

Time complexity is typically O(m log n), dominated by the initial sort of the edges, with near-constant amortized time for union-find operations, yielding O(m α(n)) in practice, where α is the inverse Ackermann function. Kruskal's algorithm is often preferred for sparse graphs, while Prim's algorithm can be more efficient on dense graphs. A key property underlying its correctness is the cycle and cut properties of minimum spanning trees.

Applications include network design, such as laying out cheapest feasible wiring or fiber layouts, and hierarchical clustering via single-link clustering, where the method iteratively connects nearby elements to form a tree-like structure.