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

Алгоритм Прима — алгоритм поиска минимального остовного дерева во взвешенном неориентированном связном графе.

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

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

Начинаем с пустого множества U. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U.
Положить в U любую вершину;   // изначально U - пусто.
while ( V-U не пусто )
{
  Выбрать ребро (u, v) наименьшей стоимости, 
  u из U, v из V-U;
  Добавить v к U (и убрать из V-U); 
}

Данный алгоритм имеет сложность O(V2)