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

Материал из WEGA
Перейти к навигации Перейти к поиску

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

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

Литература

[Кристофидес],

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