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

More information Image, Description ...
Remove ads

References

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads