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.
Class | Minimum spanning tree algorithm |
---|---|
Data structure | Graph |
Worst-case performance |
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.