Алгоритм Прима

Алгоритм Прима (R.C.Prim) - алгоритм нахождения каркаса наименьшего веса графа путем наращивания поддерева (фрагмента каркаса) за счет присоединения граничного ребра (т.е. ребра, только один конец которого принадлежит фрагменту каркаса) с наименьшим весом.

На основе А.П. созданы многочисленные модификации.

Литература

[Кристофидес], [Евстигнеев-Касьянов/94]