Kruskal

Kruskal's algorithm is a greedy method in graph theory for finding a minimum spanning tree (MST) of a connected weighted undirected graph. If the input graph is disconnected, the algorithm produces a minimum spanning forest, consisting of MSTs for each connected component.

It works by first sorting all edges in non-decreasing order of weight. It maintains a collection of disjoint components (initially, each vertex is its own component). The algorithm processes edges in order of increasing weight and adds an edge to the growing forest if it connects two different components, thereby not forming a cycle. The connected components are merged with a union operation. The process continues until all vertices are connected (or until enough edges have been added).

Correctness is based on the cut property of MSTs: for any cut that partitions the vertices into two parts, the lightest edge crossing the cut belongs to some MST; Kruskal's algorithm greedily adds such edges. It also ensures no cycles are formed by the disjoint-set data structure.

Complexity: Sorting edges dominates the running time, giving O(E log E) time, which is O(E log V). With a fast union-find structure (path compression and union by rank), the amortized cost of each operation is nearly constant, yielding near-linear performance. Memory usage is O(V + E).

History and scope: The algorithm was devised by Joseph B. Kruskal and published in 1956 as "On the shortest spanning subtree of a graph." It is one of several MST algorithms, alongside Prim's and Boruvka's algorithms, and is widely used in network design, clustering, and other computational problems requiring MSTs.