Kruskal’s minimum spanning tree algorithm
E1045593
Kruskal’s minimum spanning tree algorithm is a classic greedy graph algorithm that builds a minimum spanning tree by repeatedly adding the smallest-weight edge that does not create a cycle, typically implemented efficiently using a union–find data structure.
Observed surface forms (2)
| Surface form | Occurrences |
|---|---|
| Kruskal's algorithm | 2 |
| Kruskal's algorithm for minimum spanning trees | 1 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
graph algorithm
ⓘ
greedy algorithm ⓘ minimum spanning tree algorithm ⓘ |
| algorithmParadigm | greedy ⓘ |
| alsoKnownAs | Kruskal’s algorithm NERFINISHED ⓘ |
| assumes | edge weights are comparable ⓘ |
| avoids | cycles ⓘ |
| canHandle | graphs with equal edge weights ⓘ |
| canProduce | multiple valid minimum spanning trees when weights are not unique ⓘ |
| category | combinatorial optimization algorithm ⓘ |
| conditionForAddingEdge | edge connects two different components ⓘ |
| contrastWith | Prim’s algorithm which grows a tree from a starting vertex ⓘ |
| correctnessBasedOn |
cut property of minimum spanning trees
ⓘ
greedy-choice property ⓘ |
| edgeSelectionOrder | global order by weight ⓘ |
| field |
computer science
ⓘ
graph theory ⓘ |
| goal |
find minimum spanning tree
ⓘ
minimize total edge weight ⓘ |
| input | connected weighted undirected graph ⓘ |
| introducedInYear | 1956 ⓘ |
| keyOperation |
check whether two vertices are in the same component
ⓘ
repeatedly add smallest-weight edge that does not create a cycle ⓘ sort edges by nondecreasing weight ⓘ |
| namedAfter | Joseph Kruskal NERFINISHED ⓘ |
| operatesOn |
undirected graph
ⓘ
weighted graph ⓘ |
| optimalFor | sparse graphs ⓘ |
| output |
minimum spanning forest
ⓘ
minimum spanning tree ⓘ |
| publishedIn | Proceedings of the American Mathematical Society NERFINISHED ⓘ |
| relatedTo |
Borůvka’s algorithm
NERFINISHED
ⓘ
Prim’s minimum spanning tree algorithm NERFINISHED ⓘ |
| requires | sorting of all edges ⓘ |
| spaceComplexity | O(V) ⓘ |
| stoppingCondition | when spanning tree has |V|-1 edges ⓘ |
| taughtIn |
graph theory courses
ⓘ
undergraduate algorithms courses ⓘ |
| timeComplexity |
O(E log E)
ⓘ
O(E log V) ⓘ |
| typicalImplementationDetail |
path compression in union–find
ⓘ
union by rank in union–find ⓘ |
| usedIn |
approximation algorithms for NP-hard problems
ⓘ
clustering ⓘ network design ⓘ |
| usesDataStructure |
disjoint-set data structure
ⓘ
union–find data structure ⓘ |
| worksFor | disconnected graphs to produce a minimum spanning forest ⓘ |
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
John B. Kruskal
this entity surface form:
Kruskal's algorithm
subject surface form:
John B. Kruskal
this entity surface form:
Kruskal's algorithm for minimum spanning trees