Kruskal's algorithm
Animation of Kruskal's algorithm on a complete graph with weights based on Euclidean distance | |
| Class | Minimum spanning tree algorithm |
|---|---|
| Data structure | Graph |
| Worst-case performance | |
Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. It is a greedy algorithm that in each step adds to the forest the lowest-weight edge that will not form a cycle. The key steps of the algorithm are sorting and the use of a disjoint-set data structure to detect cycles. Its running time is dominated by the time to sort all of the graph edges by their weight.
A minimum spanning tree of a connected weighted graph is a connected subgraph, without cycles, for which the sum of the weights of all the edges in the subgraph is minimal. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.
This algorithm was first published by Joseph Kruskal in 1956, and was rediscovered soon afterward by Loberman & Weinberger (1957). Other algorithms for this problem include Prim's algorithm, Borůvka's algorithm, and the reverse-delete algorithm.