NIST

Prim-Jarnik algorithm

(algorithm)

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.)
greedy algorithm.

See also Kruskal's algorithm.

Author: JLG

Implementation

explanation and implementation (pseudocode and Java bytecode)

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

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