Kruskal's algorithm
minimum spanning forest algorithm that greedily adds edges From Wikipedia, the free encyclopedia
Remove ads
Kruskal's algorithm is a greedy algorithm to find a minimum spanning tree in a weighted, undirected graph. Joseph Kruskal first described it in 1956:
Perform the following step as many times as possible: Among the edges (..) not yet chosen, choose the shortest edge, which does not form any loops with those edges already chosen
— Kruskal, 1956[1]
In this case, the shortest edge is the one with the lowest weight.
Remove ads
Example
Download the example data. Archived 2012-07-16 at the Wayback Machine
Remove ads
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads