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 Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
Credited To
Source Wikipedia, Kruskal's algorithm
In Field
Source Wikipedia, Kruskal's algorithm
Invented By
Joseph Kruskal published the minimum spanning tree algorithm bearing his name in 1956.
Uses Design Technique
Sources
1. Kruskal's Algorithm (Wikipedia)
Wikipedia infobox: time complexity linearithmic
linearithmic
Wikipedia: design technique greedy
greedy
View the Source2. 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.
In Field: Algorithms and Complexity Theory, Lead sentence
Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph.
Credited To: Joseph Kruskal, Lead paragraph
This algorithm was first published by Joseph Kruskal in 1956
View the SourceWikidata: Kruskal's Algorithm
Wikidata Q797860, class allow-list match (w-wdresolver-0926)View the Source Reader 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.