= Kruskal's algorithm
{c}
{wiki}
= Kruskal algorithm
{c}
{synonym}
<Kruskal's algorithm> constructs a <minimum spanning tree> of a finite <connected graph> with undirected <edges> and real <edge> weights. Start with all <vertices> and no <edges>, a <forest> of isolated <vertices>. Sort the <edges> by nondecreasing weight, then accept an <edge> exactly when its endpoints belong to different current <connected components of a graph>. Otherwise reject it: the existing <graph path> between its endpoints would close a <graph cycle>. Each acceptance merges two <connected components of a graph>. Stop after $|V|-1$ acceptances, when the <forest> has become one <spanning tree>.
This is a <greedy algorithm> for economical network connection: only the next affordable connection and the current <connected components of a graph> matter. Unlike <Prim's algorithm>, which grows one reached <tree>, <Kruskal's algorithm> can grow several separate <trees> before joining them. The essential safeguard is avoiding a <graph cycle>, rather than simply buying the cheapest fixed number of <edges>.
<Joseph Bernard Kruskal> described this rule as Construction A on page 49 of his February 1956 paper, https://www.ams.org/journals/proc/1956-007-01/S0002-9939-1956-0078686-7/S0002-9939-1956-0078686-7.pdf[On the shortest spanning subtree of a graph and the traveling salesman problem]; page 50 gives an exchange argument for distinct weights.https://langevin.univ-tln.fr/cours/graphe/bonus/Krukskal.pdf[Joseph B. Kruskal, Jr., Proceedings of the American Mathematical Society 7(1), February 1956, pp. 48–50; inspected scan, Construction A and final exchange argument]{ref}
Back to article page
