Definition: Compute a minimum spanning tree by beginning with any vertex as the current tree. At each step add a least edge between any vertex not in the tree and any vertex in the tree. Continue until all vertices have been added.
Aggregate child (... is a part of or used in me.)
See also Kruskal's algorithm.
Eppstein's lecture outlining and contrasting MST algorithms.
V. Jarník, O jistem problemu minimalnim, Praca Moravske Prirodovedecke Spolecnosti, 6:57-63, 1930. (in Czech)
R. C. Prim, Shortest connection networks and some generalizations, Bell Syst. Tech. J., 36:1389-1401, 1957.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 August 2008.
HTML page formatted Fri Feb 23 10:06:08 2018.
Cite this as:
Joseph L. Ganley, "Prim-Jarnik algorithm", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/primJarnik.html