2. Алгоритм Краскала для поиска каркаса минимального веса

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

Опишем алгоритм Краскала для построения одного каркаса минимального веса. Будем считать, что исходный связный граф G задан списком ребер. Получающийся каркас тоже будет задан списком ребер. Алгоритм Краскала предусматривает построение двух последовательностей множеств ребер исходного графа: $T_1,T_2,T_3,...$ и $E_1,E_2,E_3,...$, при этом на некотором шаге одно из множеств $T_k$ оказывается каркасом минимального веса, после чего исполнение алгоритма завершается.

 

На первом шаге выбираем ребро $e_1$ наименьшего веса (если таких ребер несколько, то берем любое из них) и полагаем $T_1=\left\{e_1\right\}$. В качестве множества $E_1$ строится множество ребер, каждое из которых не содержится в $T_1$ и при добавлении к $T_1$ не образует цикл.

 

Пусть уже построены множества $T_1,T_2,...,T_k$ и $E_1,E_2,...,E_k$. Если множество $E_k$ не содержит ребро, то в качестве искомого каркаса берем множество $T_k$. Если же множество $E_k$ не пусто, то строим $T_{k+1}$ и $E_{k+1}$ по следующему правилу: в множестве $E_k$ выбираем ребро наименьшего веса (если таких ребер несколько, то снова берем любое из них) и добавляем его в множество $T_k$, это и будет множество $T_{k+1}$; множество $E_{k+1}$ состоит из таких ребер, что каждое из них не содержится в $T_{k+1}$ и при добавлении любого из них к множеству $T_{k+1}$ не образует цикл. Такое построение последовательности множеств $T_k$ и $E_k$ повторяются, пока множество $E_k$ не станет пустым.

 

Алгоритм Прима. В этом методе поиска каркаса минимального веса при построении очередного множества $E_k$ в него включаются только те ребра, которые не содержатся в $T_k$, не образуют цикл при добавлении к $T_k$ и имеют общую вершину хотя бы с одним ребром из $T_k$.