|
gptkbp:instanceOf
|
gptkb:algorithm
graph
|
|
gptkbp:alsoKnownAs
|
gptkb:Jarník's_algorithm
|
|
gptkbp:appliesTo
|
undirected graphs
connected graphs
|
|
gptkbp:approach
|
greedy
|
|
gptkbp:category
|
combinatorial optimization
network design
|
|
gptkbp:compatibleWith
|
directed graphs
disconnected graphs
|
|
gptkbp:complexity
|
O(E + V log V) with Fibonacci heap
O(V^2) with adjacency matrix
|
|
gptkbp:complexityDependsOn
|
data structure used
|
|
gptkbp:distinctFrom
|
Dijkstra's Algorithm finds shortest paths, Prim's finds minimum spanning tree
|
|
gptkbp:field
|
computer science
graph theory
|
|
gptkbp:firstPublished
|
1957
|
|
gptkbp:guarantees
|
optimal solution
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Prim's Algorithm
|
|
gptkbp:implementedIn
|
gptkb:binary_heap
Fibonacci heap
adjacency matrix
adjacency list
|
|
gptkbp:input
|
connected weighted undirected graph
|
|
gptkbp:isDeterministic
|
true
|
|
gptkbp:isGreedy
|
true
|
|
gptkbp:isIterative
|
true
|
|
gptkbp:isNotRecursive
|
true
|
|
gptkbp:isNPComplete
|
false
|
|
gptkbp:isOfflineAlgorithm
|
true
|
|
gptkbp:isOnlineAlgorithm
|
false
|
|
gptkbp:isP
|
true
|
|
gptkbp:isPolynomialTime
|
true
|
|
gptkbp:namedAfter
|
gptkb:Robert_C._Prim
|
|
gptkbp:output
|
minimum spanning tree
|
|
gptkbp:programmingLanguage
|
true
|
|
gptkbp:publicationYear
|
1930
|
|
gptkbp:publisher
|
gptkb:Vojtěch_Jarník
|
|
gptkbp:relatedTo
|
gptkb:Kruskal's_Algorithm
|
|
gptkbp:requires
|
priority queue
|
|
gptkbp:similarTo
|
gptkb:Dijkstra's_Algorithm
|
|
gptkbp:solvedBy
|
minimum spanning tree problem
|
|
gptkbp:step
|
repeats until all vertices included
starts from arbitrary vertex
adds minimum weight edge connecting tree to new vertex
|
|
gptkbp:usedIn
|
clustering
circuit design
approximation algorithms
network design
|
|
gptkbp:bfsParent
|
gptkb:Spanning_Tree_Algorithm
gptkb:Graph_Algorithms
|
|
gptkbp:bfsLayer
|
6
|