Kruskal’s minimum spanning tree algorithm

E1045593

graph algorithm greedy algorithm minimum spanning tree algorithm

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.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (3)

Label	Occurrences
Kruskal's algorithm	2
Kruskal's algorithm for minimum spanning trees	1
Kruskal’s minimum spanning tree algorithm canonical	1

How this entity was disambiguated

This entity first appeared as the object of triple T13507145 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Kruskal’s minimum spanning tree algorithm
Context triple: [union–find data structure, usedInAlgorithm, Kruskal’s minimum spanning tree algorithm]

A. Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
B. union–find data structure
The union–find data structure is an efficient algorithmic structure that maintains disjoint sets and supports fast union and find operations, widely used in graph algorithms such as Kruskal’s minimum spanning tree.
C. Steiner tree problem
The Steiner tree problem is a classic optimization problem in combinatorial mathematics and computer science that seeks the shortest network of line segments connecting a given set of points, potentially adding extra intermediate points to minimize total length.
D. Tarjan's strongly connected components algorithm
Tarjan's strongly connected components algorithm is a classic linear-time graph algorithm that efficiently identifies all strongly connected components in a directed graph using depth-first search and low-link values.
E. Cristian's algorithm
Cristian's algorithm is a clock synchronization method in distributed systems that estimates accurate time on client machines by querying a time server and adjusting for message delays.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Kruskal’s minimum spanning tree algorithm
Target entity description: 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.

A. Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
B. union–find data structure
The union–find data structure is an efficient algorithmic structure that maintains disjoint sets and supports fast union and find operations, widely used in graph algorithms such as Kruskal’s minimum spanning tree.
C. Steiner tree problem
The Steiner tree problem is a classic optimization problem in combinatorial mathematics and computer science that seeks the shortest network of line segments connecting a given set of points, potentially adding extra intermediate points to minimize total length.
D. Tarjan's strongly connected components algorithm
Tarjan's strongly connected components algorithm is a classic linear-time graph algorithm that efficiently identifies all strongly connected components in a directed graph using depth-first search and low-link values.
E. Cristian's algorithm
Cristian's algorithm is a clock synchronization method in distributed systems that estimates accurate time on client machines by querying a time server and adjusting for message delays.
F. None of above. chosen

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 ⓘ

How these facts were elicited

Referenced by (4)

Full triples — surface form annotated when it differs from this entity's canonical label.

union–find data structure → usedInAlgorithm → Kruskal’s minimum spanning tree algorithm ⓘ

John Kruskal → notableFor → Kruskal’s minimum spanning tree algorithm ⓘ

subject surface form: John B. Kruskal

this entity surface form: Kruskal's algorithm

John Kruskal → notableWork → Kruskal’s minimum spanning tree algorithm ⓘ

subject surface form: John B. Kruskal

this entity surface form: Kruskal's algorithm for minimum spanning trees

Kruskal → knownFor → Kruskal’s minimum spanning tree algorithm ⓘ

subject surface form: Joseph B. Kruskal