Kruskal's algorithm[1] finds a minimum spanning forest of an undirected edge-weighted graph.

It is a greedy algorithm that in each step adds to the forest the lowest-weight edge that will not form a cycle.

[2] The key steps of the algorithm are sorting and the use of a disjoint-set data structure to detect cycles.

This algorithm was first published by Joseph Kruskal in 1956,[3] and was rediscovered soon afterward by Loberman & Weinberger (1957).

If the graph is connected, the forest has a single component and forms a minimum spanning tree.

It represents the forest F as a set of undirected edges, and uses the disjoint-set data structure to efficiently determine whether two vertices are part of the same tree.

Creating this structure, with a separate set for each vertex, takes V operations and O(V) time.

We show that the following proposition P is true by induction: If F is the set of edges chosen at any stage of the algorithm, then there is some minimum spanning tree that contains F and none of the edges rejected by the algorithm.

It is, however, possible to perform the initial sorting of the edges in parallel or, alternatively, to use a parallel implementation of a binary heap to extract the minimum-weight edge in every iteration.

A variant of Kruskal's algorithm, named Filter-Kruskal, has been described by Osipov et al.[7] and is better suited for parallelization.

[7] Finally, other variants of a parallel implementation of Kruskal's algorithm have been explored.

Examples include a scheme that uses helper threads to remove edges that are definitely not part of the MST in the background,[8] and a variant which runs the sequential algorithm on p subgraphs, then merges those subgraphs until only one, the final MST, remains.