A greedy algorithm for finding a minimum spanning tree of a weighted graph, sorting every edge by weight and adding each one in turn as long as it does not close a cycle, tracked efficiently with a disjoint-set structure.
Facts
Time Complexity Classification
Design Technique Connections
Invented
Joseph Kruskal published the minimum spanning tree algorithm bearing his name in 1956.
Sources
1. Wikipedia, Kruskal's algorithm
Lead section
This algorithm was first published by Joseph Kruskal in 1956, and was rediscovered soon afterward by Loberman & Weinberger (1957).
Complexity
For a graph with E edges and V vertices, Kruskal's algorithm can be shown to run in time O(E log E) time, with simple data structures.
entity record, description (design-technique)
A greedy algorithm for finding a minimum spanning tree of a weighted graph, sorting every edge by weight and adding each one in turn as long as it does not close a cycle, tracked efficiently with a disjoint-set structure.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.