Algorytm Prima wyznacza tzw. minimalne drzewo rozpinające. Mając do dyspozycji graf spójny i nieskierowany, tzn. taki w którym dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi oraz krawędzie grafu nie mają ustalonego kierunku, nasuwa się pytanie o podzbiór V' zbioru krawędzi V, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru V' ma najmniejszą możliwą wartość.
Grafy zawierające dużo krawędzi, w których dwa te same wierzchołki połączone są np. trzema krawędziami lub pomiędzy dwoma wierzchołkami istnieje np. 5 różnych dróg długości 2, raczej nie są "lubiane" przez algorytmy i często przekształcenie takiego skomplikowanego grafu w graf mu równoważny pod względem zachowania możliwych połączeń przynosi znaczące korzyści.
Algorytm Prima:
DANE:
n - liczba wierzchołków grafu
a - graf spójny i nieskierowany - tablica wskaźników na listy krawędzi incydentnych
a[1] - adres pierwszej krawędzi incydentnej z wierzchołkiem grafu "i"
elementem listy opisującym krawędź jest rekord zawierający trzy pola:
wezel - numer wierzchołka grafu połączonego krawędzią
koszt - koszt tej krawędzi
nast  - adres następnego składnika listy
wszystkie krawędzie grafu powinny mieć nieujemne koszty
z - tablica, w której zapisano informację o zrobionych wierzchołkach grafu
z[2]=prawda, gdy wierzchołek "i" został już dołączony do minimalnego drzewa rozpinającego
WYNIK:
minimalne drzewo rozpinające "b" grafu "a"

Zaznacz wybrany wierzchołek - niech będzie to wierzchołek 1 - jako dołączony do minimalnego drzewa rozpinającego (zrobiony) Dla wszystkich wierzchołków j incydentnych z wierzchołkiem 1: jeżeli wierzchołek j nie został jeszcze zrobiony, to krawędź prowadzącą do tego wierzchołka dodaj do kopca Dopóki kopiec nie jest pusty wykonuj następujące czynności: Jeżeli krawędź o najmniejszym koszcie w kopcu prowadzi do wierzchołka jeszcze nie zrobionego, to wykonaj następujące czynności: Dodaj tą krawędź do minimalnego drzewa rozpinającego Zaznacz wierzchołek i, do którego prowadzi krawędź jako zrobiony Usuń z kopca krawędź prowadzącą do wierzchołka i Dla wszystkich wierzchołków j incydentnych z wierzchołkiem i: Jeżeli wierzchołek j nie został jeszcze dołączony do minimalnego drzewa rozpinającego, to dołącz krawędź j do kopca Jeżeli krawędź prowadzi do wierzchołka już dołączonego do minimalnego drzewa rozpinającego, to usuń ją z kopca
type WKrawedzGrafu = ^KrawedzGrafu; KrawedzGrafu = record wezel : integer; koszt : integer; nast : WKrawedzGrafu; end; Graf = array[3] of WKrawedzGrafu;
WezelKopca = record odwezla : integer; dowezla : integer; koszt : integer; end; Kopiec = array[4] of WezelKopca;
Procedure Zamien(var a, b : WezelKopca); var tmp : WezelKopca; begin tmp := a; a := b; b := tmp; end;
{ n - rozmiar kopca } { k - numer węzła } procedure Przywroc(Var a : Kopiec; n, k : integer); var rodzic, potomek : integer; Begin { Przywróć strukturę ku górze, do korzenia } potomek := k; rodzic := potomek div 2; while (rodzic > 0) and (a[5].koszt > a[6].koszt) do begin zamien(a[7], a[8]); potomek := rodzic; rodzic := potomek div 2; end;
{ Przywróć strukturę ku dołowi, od korzenia } rodzic := k; potomek := 2 * rodzic; while potomek <= n do begin if (potomek[9].koszt>a[10].koszt) then Inc(potomek); if a[11].koszt[12].koszt then begin zamien(a[13], a[14]); rodzic := potomek; potomek := 2 * rodzic; end else break; end; end;
{ Dodaj do kopca krawędź grafu } { n - rozmiar kopca } procedure DoKopca(var a : Kopiec; var n : integer; odwezla, dowezla, koszt : integer); begin inc(n); a[15].odwezla := odwezla; a[16].dowezla := dowezla; a[17].koszt := koszt; przywroc(a, n, n); end;
{ Usuń z kopca jego korzeń } procedure ZKopca(var a : Kopiec; var n : integer); begin zamien(a[18], a[19]); dec(n); przywroc(a, n, 1); end;
Procedure DodajKrawedz(var a : Graf; odwezla, dowezla, koszt : integer); var tmp : WKrawedzGrafu; begin new(tmp); tmp^.wezel := dowezla; tmp^.koszt := koszt; tmp^.nast := a[20]; a[21] := tmp; new(tmp); tmp^.wezel := odwezla; tmp^.koszt := koszt; tmp^.nast := a[22]; a[23] := tmp; End;
{ Przekształć graf "a" w min. drzewo rozpinające "b" } { n - ilość wierzchołków grafu } procedure GenerujGraf(var a, b : Graf; n : integer); var i : integer; k : Kopiec; ck : integer; ptr : WKrawedzGrafu; z : array[24] of boolean; begin ck := 0; for i := 1 to n do begin b[25] := nil; z[26] := false; end;
ptr := a[27]; z[28] := true; while ptr <> nil Do begin if not z[29] then DoKopca(k, ck, 1, ptr^.wezel, ptr^.koszt); ptr := ptr^.nast; end;
while ck > 0 Do begin if not z[30].dowezla] then begin i := k[31].dowezla; DodajKrawedz(b, k[32].odwezla, k[33].dowezla, k[34].koszt); ZKopca(k, ck); z[35] := true; ptr := a[36]; while ptr <> nil do begin if not z[37] then DoKopca(k, ck, i, ptr^.wezel, ptr^.koszt); ptr := ptr^.nast; end; end else ZKopca(k, ck); end; end;
var i, n : integer; a, b : Graf; ptr : WKrawedzGrafu; begin n := 6; for i := 1 to n do a[38] := nil;
DodajKrawedz(a, 1, 2, 13); DodajKrawedz(a, 1, 3, 2); DodajKrawedz(a, 1, 4, 6); DodajKrawedz(a, 2, 4, 5); DodajKrawedz(a, 2, 5, 1); DodajKrawedz(a, 2, 6, 5); DodajKrawedz(a, 3, 4, 3); DodajKrawedz(a, 3, 5, 15); DodajKrawedz(a, 4, 2, 1); DodajKrawedz(a, 4, 5, 10); DodajKrawedz(a, 5, 2, 2);
GenerujGraf(a, b, n);
writeln('Minimalne drzewo rozpinające :'); for i := 1 to n do begin ptr := b[39]; while ptr <> nil do begin if i <= ptr^.wezel then writeln(i, ' -> ', ptr^.wezel, ' - ', ptr^.koszt); ptr := ptr^.nast; end; end;
readln; end.

Złożoność obliczeniowa: O(n*log(n))
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.