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)
Блок-схема алгоритма
Код программы
#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), что асимптотически совпадает со временем работы алгоритма Крускала.
