Papalocal
Loading…
Papalocal · Things
Work

Kruskal's algorithm

Kruskal's algorithm is a minimum spanning forest algorithm that greedily adds edges. It came out in 1956.

Released
1956
All 4 facts, and where they come from

Facts

4 facts · 0 confirmed by two sources · 0 cited · 4 from one source

What it is
greedy algorithm One source
graph algorithm One source
Released
1956 One source
Named after
Joseph Kruskal One source

Where this comes from

Papalocal keeps its own record. It started from these sources; what each one said is kept here as it was copied, so a change on their side never changes this page by itself. Tap one to read its version.

What Wikidata says · copied November 17, 2026 · revision 2473970312
Described as
minimum spanning forest algorithm that greedily adds edges
What it is
greedy algorithm; graph algorithm
Released
1956
Named after
Joseph Kruskal
Wikipedias with a page
31

Wikidata item Q797860 (wikidata.org/wiki/Q797860), public domain (CC0). Copied 2026-11-17.

What Wikipedia says · copied November 17, 2026 · revision 1383615701

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.

From the Wikipedia article “Kruskal's algorithm” (en.wikipedia.org/wiki/Kruskal's_algorithm), by its contributors, under CC BY-SA 4.0 (creativecommons.org/licenses/by-sa/4.0/). Copied 2026-11-17; not changed.

Confirmed Two sources agree. Cited One source, and it names where it got it. One source One source, without a reference of its own. Sources disagree The sources disagree. We show the best-supported value and keep theirs below.

Picture: Wikimedia Commons: MST kruskal en.gif · See Commons file page

People connected 1

Known for it