Prim's minimum spanning tree algorithm
E1047207
Prim's minimum spanning tree algorithm is a greedy graph algorithm that incrementally builds a minimum-cost spanning tree by repeatedly adding the cheapest edge connecting the growing tree to a new vertex.
All labels observed (5)
| Label | Occurrences |
|---|---|
| Jarník–Prim algorithm | 1 |
| Prim's algorithm | 1 |
| Prim's minimum spanning tree algorithm canonical | 1 |
| Prim–Dijkstra algorithm | 1 |
| Prim’s minimum spanning tree algorithm | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T13507194 — 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: Prim's minimum spanning tree algorithm Context triple: [Fibonacci heap, usedInAlgorithm, Prim's minimum spanning tree algorithm]
-
A.
Kruskal’s 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.
-
B.
Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
-
C.
Dijkstra's shortest path algorithm
Dijkstra's shortest path algorithm is a classic graph algorithm that efficiently computes the minimum-cost paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
-
D.
Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
-
E.
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.
- 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: Prim's minimum spanning tree algorithm Target entity description: Prim's minimum spanning tree algorithm is a greedy graph algorithm that incrementally builds a minimum-cost spanning tree by repeatedly adding the cheapest edge connecting the growing tree to a new vertex.
-
A.
Kruskal’s 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.
-
B.
Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
-
C.
Dijkstra's shortest path algorithm
Dijkstra's shortest path algorithm is a classic graph algorithm that efficiently computes the minimum-cost paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
-
D.
Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
-
E.
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.
- F. None of above. chosen
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
graph algorithm
ⓘ
greedy algorithm ⓘ minimum spanning tree algorithm ⓘ |
| alsoKnownAs |
Jarník–Prim algorithm
ⓘ
linked to:
Prim's minimum spanning tree algorithm
Prim's algorithm ⓘ
linked to:
Prim's minimum spanning tree algorithm
Prim–Dijkstra algorithm ⓘ
linked to:
Prim's minimum spanning tree algorithm
|
| application |
circuit design
ⓘ
network design ⓘ telecommunications ⓘ transportation networks ⓘ |
| behaviorOnDisconnectedGraph | produces minimum spanning forest ⓘ |
| coreIdea | grow a tree by repeatedly adding the cheapest edge from the tree to a new vertex ⓘ |
| correctnessBasedOn | cut property of minimum spanning trees ⓘ |
| dataStructureOption |
Fibonacci heap
ⓘ
adjacency list ⓘ adjacency matrix ⓘ binary heap ⓘ priority queue ⓘ |
| differenceFromKruskal | grows a single tree instead of a forest ⓘ |
| edgeType | undirected edges ⓘ |
| failsOn | graphs with negative cycles is not applicable conceptually but MST ignores cycles ⓘ |
| guarantees | globally optimal minimum spanning tree ⓘ |
| handles |
graphs with distinct edge weights
ⓘ
graphs with equal edge weights ⓘ |
| input |
connected weighted undirected graph
ⓘ
graph with non-negative edge weights ⓘ |
| maintains |
cut between tree vertices and non-tree vertices
ⓘ
set of vertices already in the tree ⓘ |
| namedAfter |
Robert C. Prim
ⓘ
linked to:
Delbert Ray Fulkerson
|
| originalDiscoveryYear | 1930 ⓘ |
| originallyDiscoveredBy | Vojtěch Jarník ⓘ |
| output |
minimum spanning tree
ⓘ
spanning tree of minimum total edge weight ⓘ |
| relatedTo |
Borůvka's algorithm
ⓘ
linked to:
Borůvka’s algorithm
Kruskal's minimum spanning tree algorithm ⓘ
linked to:
Kruskal’s minimum spanning tree algorithm
|
| requiresGraphProperty | connectedness for full spanning tree ⓘ |
| selects | minimum-weight edge crossing the cut ⓘ |
| solves | minimum spanning tree problem ⓘ |
| spaceComplexity | O(V + E) ⓘ |
| startsFrom | arbitrary vertex ⓘ |
| strategy | greedy ⓘ |
| timeComplexityWithAdjacencyMatrix | O(V^2) ⓘ |
| timeComplexityWithBinaryHeap | O(E log V) ⓘ |
| timeComplexityWithFibonacciHeap | O(E + V log V) ⓘ |
| typicalUseCase | dense graphs ⓘ |
| usedIn |
graph theory education
ⓘ
introductory algorithms courses ⓘ |
| yearIntroduced | 1957 ⓘ |
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: Prim's minimum spanning tree algorithm Description of subject: Prim's minimum spanning tree algorithm is a greedy graph algorithm that incrementally builds a minimum-cost spanning tree by repeatedly adding the cheapest edge connecting the growing tree to a new vertex.
Referenced by (5)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Prim's minimum spanning tree algorithm
linked to: Prim's minimum spanning tree algorithm
linked to: Prim's minimum spanning tree algorithm
linked to: Prim's minimum spanning tree algorithm