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.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
graph algorithm
ⓘ
greedy algorithm ⓘ minimum spanning tree algorithm ⓘ |
| alsoKnownAs |
Jarník–Prim algorithm
NERFINISHED
ⓘ
Prim's algorithm NERFINISHED ⓘ Prim–Dijkstra algorithm NERFINISHED ⓘ |
| 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
NERFINISHED
ⓘ
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 NERFINISHED ⓘ |
| originalDiscoveryYear | 1930 GENERATED ⓘ |
| originallyDiscoveredBy | Vojtěch Jarník GENERATED ⓘ |
| output |
minimum spanning tree
ⓘ
spanning tree of minimum total edge weight ⓘ |
| relatedTo |
Borůvka's algorithm
NERFINISHED
ⓘ
Kruskal's minimum spanning tree algorithm NERFINISHED ⓘ |
| 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 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.