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