Алгоритм Прима. 
Алгоритм Краскала

Описание алгоритма Прима

Описание.

Сам алгоритм имеет очень простой вид. Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т. е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что-то же самое, n-1 ребро).

В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется меньше n-1).

Вход: Связный неориентированный граф G (V, E).

Выход: Множество T рёбер минимального остовного дерева Алгоритм.

• · Множество остовных вершин — исходная вершины
• · Множество оставшихся — все вершины за исключением исходной
• · Пока множество оставшихся не пусто:
  • o Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес
  • o Для найденного ребра, вершину принадлежащую множеству оставшихся:
• · Вычеркиваем из множества оставшихся.
• · Добавляем к множеству остовных.

выбрать начальный узел сформировать начальную кайму, состоящую из вершин, соседних с начальным узлом.

while в графе есть вершины, не попавшие в дерево do.

выбрать ребро из дерева в кайму с наименьшим весом добавить конец ребра к дереву изменить кайму, для чего добавить в кайму вершины, соседние с новой обновить список ребер из дерева в кайму так, чтобы он состоял из ребер наименьшего веса.

end while.