|
gptkbp:instanceOf
|
gptkb:algorithm
graph
minimum spanning tree algorithm
|
|
gptkbp:alsoKnownAs
|
gptkb:Jarník's_algorithm
|
|
gptkbp:category
|
greedy algorithm
|
|
gptkbp:complexity
|
O(E + V log V)
O(V^2)
|
|
gptkbp:complexityDependsOn
|
data structure used
|
|
gptkbp:firstPublished
|
gptkb:Vojtěch_Jarník
1930
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Prim's algorithm
|
|
gptkbp:implementedIn
|
gptkb:Java
gptkb:Python
gptkb:C++
C
many programming languages
|
|
gptkbp:input
|
connected weighted undirected graph
|
|
gptkbp:namedAfter
|
gptkb:Robert_C._Prim
|
|
gptkbp:output
|
minimum spanning tree
|
|
gptkbp:programmingLanguage
|
yes
|
|
gptkbp:relatedTo
|
gptkb:Kruskal's_algorithm
gptkb:Borůvka's_algorithm
|
|
gptkbp:restored
|
gptkb:Robert_C._Prim
1957
|
|
gptkbp:solvedBy
|
minimum spanning tree problem
|
|
gptkbp:step
|
grows tree by adding minimum weight edge
repeats until all vertices included
starts from arbitrary vertex
|
|
gptkbp:usedIn
|
circuit design
approximation algorithms
network design
cluster analysis
|
|
gptkbp:usesDataStructure
|
priority queue
min-heap
|
|
gptkbp:bfsParent
|
gptkb:Graph_theory
|
|
gptkbp:bfsLayer
|
5
|