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

MST_PRIM (G, w, r).

• 1 for (Для) каждой вершины u є V[G]
• 2 do key [u] «- INFINITY
• 3 prev[u] «- NIL
• 4 key[r] «- 0
• 5 Q «- V[G]
• 6 while Q не пустая
• 7 do u «- Extract_Min (Q)
• 8 for (Для) каждой вершины v є Adj[u]
• 9 do if v є Q и w (u, v) < key[v]
• 10 then prev[v] «- u
• 11 key[v] «- w (u, v)

Блок-схема алгоритма

• 1
• 1
• 1
• 1
• 1
• 1

Код программы

#include.

#include.

#include.

#define forn (i, n) for (int i=0;i.

using namespace std;

int n, m;

vector g[500]; //кроме вершин список смежности хранит и вес ребра.

vector used (500,0);//вектор использованных вершин.

int inf=10 000 000;

vector d (500,inf);//вектор расстояний.

int main ().

{.

freopen («input.txt» ," rt", stdin);

freopen («output.txt» ," wt", stdout);

cin>>n>>m;

int x, y, l;

pair temp;

forn (i, m){.

cin>>x>>y>>l;

x—;

y—;

temp.first=y;

temp.second=l;

g[x]. push_back (temp);

temp.first=x;

g[y]. push_back (temp);

}.

vector path (500);

d[0]=0;

while (true){.

int v=-1;

int dist=inf;

forn (u, n).

if (!used[u] && dist>=d[u]).

{.

v=u;

dist=d[u];

}.

if (v==-1) break;

used[v]=true;

forn (u, g[v]. size ()).

if (!used[g[v][u]. first]) {.

if (d[g[v][u]. first]>g[v][u].second) path[g[v][u]. first]=make_pair (v, g[v][u].first);

d[g[v][u]. first]=min (d[g[v][u].first], g[v][u].second);

}.

}.

long long sum=0;

forn (i, n) sum+=d[i];

cout<

forn (i, n-1).

cout<<<" «<<

return 0;

}.

Оценка сложности

Время работы алгоритма Прима зависит от выбранной реализации очереди с приоритетами Q. Если реализовать ее как бинарную пирамиду, то для выполнения инициализации в строках 1−5 потребуется времени О (V). Тело цикла while выполняется |V| раз, а поскольку каждая операция Extract_Min занимает время О (lg V), общее время всех вызовов процедур Extract__Min составляет О (V*lg V). Цикл for в строках 8−11 выполняется всего О (Е) раз, поскольку сумма длин всех списков смежности равна 2|Е|. Внутри цикла for проверка на принадлежность Q в строке 9 может быть реализована за постоянное время, если воспользоваться для каждой вершины битом, указывающим, находится ли она в Q, и обновлять этот бит при удалении вершины из Q. Присвоение в строке 11 неявно включает операцию Decrease_Key над пирамидой. Время выполнения этой операции — О (lg V). Таким образом, общее время работы алгоритма Прима составляет o (V * lg V + Е * lg V) = o (Е * lg V), что асимптотически совпадает со временем работы алгоритма Крускала.