 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[1] 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.[2] 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,[3] and was rediscovered soon afterward by Loberman & Weinberger (1957).[4] Other algorithms for this problem include Prim's algorithm, Borůvka's algorithm, and the reverse-delete algorithm.
- ^ Kleinberg, Jon (2006). Algorithm design. Éva Tardos. Boston: Pearson/Addison-Wesley. pp. 142–151. ISBN 0-321-29535-8. OCLC 57422612.
- ^ Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein (2009). Introduction To Algorithms (Third ed.). MIT Press. pp. 631. ISBN 978-0262258104.
{{cite book}}: CS1 maint: multiple names: authors list (link) - ^ Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem". Proceedings of the American Mathematical Society. 7 (1): 48–50. doi:10.1090/S0002-9939-1956-0078686-7. JSTOR 2033241.
- ^ Loberman, H.; Weinberger, A. (October 1957). "Formal Procedures for connecting terminals with a minimum total wire length". Journal of the ACM. 4 (4): 428–437. doi:10.1145/320893.320896. S2CID 7320964.