# Kruskal's algorithm

## Minimum spanning forest algorithm that greedily adds edges / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Kruskal's algorithm?

Summarize this article for a 10 year old

**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.

**Quick Facts**Class, Data structure ...

Class | Minimum spanning tree algorithm |
---|---|

Data structure | Graph |

Worst-case performance | $O(|E|\log |V|)$ |

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.