Теория:
Имеется загруженный связный граф. Требуется найти каркас с минимальным суммарным весом его ребер. Таких каркасов у данного нагруженного связного графа может быть несколько.
Пример:
Рассмотрим граф.

Рис. 1
На рисунках 2 и 3 приведены два каркаса минимального веса для графа, изображенного на рисунке 1.

Рис. 2

Рис. 3
Вес обоих минимальных каркасов одинаков и он равен \(9\).
На первом шаге выбираем ребро наименьшего веса (если таких ребер несколько, то берем любое из них) и полагаем . В качестве множества строится множество ребер, каждое из которых не содержится в и при добавлении к не образует цикл.
Пусть уже построены множества и . Если множество не содержит ребро, то в качестве искомого каркаса берем множество . Если же множество не пусто, то строим и по следующему правилу: в множестве выбираем ребро наименьшего веса (если таких ребер несколько, то снова берем любое из них) и добавляем его в множество , это и будет множество ; множество состоит из таких ребер, что каждое из них не содержится в и при добавлении любого из них к множеству не образует цикл. Такое построение последовательности множеств и повторяются, пока множество не станет пустым.
Алгоритм Прима. В этом методе поиска каркаса минимального веса при построении очередного множества в него включаются только те ребра, которые не содержатся в , не образуют цикл при добавлении к и имеют общую вершину хотя бы с одним ребром из .
Источники:
Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. - Москва: Просвещение, 2012. -235 с.