Теория:

Имеется загруженный связный граф. Требуется найти каркас с минимальным суммарным весом его ребер. Таких каркасов у данного нагруженного связного графа может быть несколько.
Пример:
Рассмотрим граф.
 
т2.png
Рис. 1
  
На рисунках 2 и 3 приведены два каркаса минимального веса для графа, изображенного на рисунке 1.
 
т2-1.png
Рис. 2 
  
т2-2.png
Рис. 3
 
Вес обоих минимальных каркасов одинаков и он равен \(9\).
Опишем алгоритм Краскала для построения одного каркаса минимального веса. Будем считать, что исходный связный граф G задан списком ребер. Получающийся каркас тоже будет задан списком ребер. Алгоритм Краскала предусматривает построение двух последовательностей множеств ребер исходного графа: T1,T2,T3,... и E1,E2,E3,..., при этом на некотором шаге одно из множеств Tk оказывается каркасом минимального веса, после чего исполнение алгоритма завершается.
 
На первом шаге выбираем ребро e1 наименьшего веса (если таких ребер несколько, то берем любое из них) и полагаем T1=e1. В качестве множества E1 строится множество ребер, каждое из которых не содержится в T1 и при добавлении к T1 не образует цикл.
 
Пусть уже построены множества T1,T2,...,Tk и E1,E2,...,Ek. Если множество Ek не содержит ребро, то в качестве искомого каркаса берем множество Tk. Если же множество Ek не пусто, то строим Tk+1 и Ek+1 по следующему правилу: в множестве Ek выбираем ребро наименьшего веса (если таких ребер несколько, то снова берем любое из них) и добавляем его в множество Tk, это и будет множество Tk+1; множество Ek+1 состоит из таких ребер, что каждое из них не содержится в Tk+1 и при добавлении любого из них к множеству Tk+1 не образует цикл. Такое построение последовательности множеств Tk и Ek повторяются, пока множество Ek не станет пустым.
 
Алгоритм Прима. В этом методе поиска каркаса минимального веса при построении очередного множества Ek в него включаются только те ребра, которые не содержатся в Tk, не образуют цикл при добавлении к Tk и имеют общую вершину хотя бы с одним ребром из Tk.
Источники:
Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. - Москва: Просвещение, 2012. -235 с.