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.
All labels observed (5)
| Label | Occurrences |
|---|---|
| Kruskal's algorithm | 2 |
| Kruskal's algorithm for minimum spanning trees | 1 |
| Kruskal's minimum spanning tree algorithm | 1 |
| Kruskal’s algorithm | 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
ⓘ
linked to:
Kruskal’s minimum spanning tree algorithm
|
| 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
ⓘ
linked to:
Joseph B. Kruskal
|
| operatesOn |
undirected graph
ⓘ
weighted graph ⓘ |
| optimalFor | sparse graphs ⓘ |
| output |
minimum spanning forest
ⓘ
minimum spanning tree ⓘ |
| publishedIn | Proceedings of the American Mathematical Society ⓘ |
| relatedTo |
Borůvka’s algorithm
ⓘ
Prim’s minimum spanning tree algorithm ⓘ
linked to:
Prim's minimum spanning tree algorithm
|
| 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
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Kruskal’s minimum spanning tree algorithm Description of subject: 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.
Referenced by (6)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject linked to:
John Kruskal
linked to: Kruskal’s minimum spanning tree algorithm
subject linked to:
John Kruskal
linked to: Kruskal’s minimum spanning tree algorithm
subject linked to:
Kruskal
linked to: Kruskal’s minimum spanning tree algorithm
linked to: Kruskal’s minimum spanning tree algorithm
linked to: Kruskal’s minimum spanning tree algorithm