Kruskal's algorithm

(algorithm)

Definition: An algorithm for computing a minimum spanning tree. It maintains a set of partial minimum spanning trees, and repeatedly adds the shortest edge in the graph whose vertices are in different partial minimum spanning trees.

See also Prim-Jarnik algorithm.

Author: JLG

Implementation

analysis and code (C), (pseudocode)

More information

Eppstein's lecture outlining and contrasting MST algorithms. Illustration and explanation.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 August 2024.
HTML page formatted Mon Aug 19 12:34:35 2024.

Cite this as:
Joseph L. Ganley, "Kruskal's algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 August 2024. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/kruskalsalgo.html