Prim algoritmusa mohó algoritmus, tehát az aktuálisan legjobbnak tűnő élt részesíti előnyben. Prim algoritmusában az $A$ halmaz élei egyetlen fát formáznak.

A fa építése egy tetszőlegesen kiválasztott gyökércsúcsból indul, és addig növekszik, amíg az összes csúcsot el nem értük. Minden lépésben azt a könnyű élt vesszük hozzá az $A$ fához, amelyik egy $A$-beli csúcsot köt össze egy $A$-n kivüli csúccsal. Ez az él könnyű él lesz, ami egyben biztonságos él is. Az $A$ fában még nem szereplő csúcsok a végrehajtás közben egy $Q$ minimum prioritásos sorban helyezkednek el. Amikor az algoritmus befejeződik, a $Q$ minimum prioritásos sor üres. Ha minden csúcsot elérünk bármelyik másikból, tehát $n$ csúcs esetén $(n-1)$ él hozzáadása után, minimális feszítőfát kapunk és leáll az algoritmus.

A csúcsokhoz címkéket rendelünk:

• $p$ a csúcs szülője
• $c$ a csúcs és a szülője közti él súlya, $c(u) = w(p(u), u)$

Ha még nem adtunk hozzá $A$-hoz olyan élt, ami összekötné az $u$ csúcsot bármelyik másikkal, akkor $p(u) = \emptyset \land c(u) = \infty$. Az algoritmus lefutása után egyik csúcs $c$ értéke sem lehet $\infty$, mert akkor az azt jelentené, hogy nem összefüggő a gráf és nem lehet elérni minden csúcsot.

Működése:

Az első ciklusban inicializáljuk minden csúcs szülőjét $\emptyset$-ra és költségét végtelenre.

A minimum prioritásos sorban eltároljuk az $A$ fában még nem szereplő csúcsokat. A kezdő csúcsot nem rakjuk bele, mert ez alapból benne lesz $A$-ban.

A második ciklus során végig nézzük az adott csúcsból kimenő éleket, és ha úgy tűnik, hogy ebből a csúcsból olcsóbb úton tudunk eljutni egy csúcsba, akkor azt frissítjük. Ilyenkor az új prioritások mentén a sort is újra kellhet rendezni.

Műveletigény:

A Prim-algoritmus hatékonysága a $Q$ prioritásos sor megvalósításán múlik. Ha $Q$-t minimum-kupacként valósítjuk meg, akkor:

• $n = |G.V|$ (csúcsok száma), $m = |G.E|$ (élek száma)
• $T(n, m) \in O(m \cdot \log n)$

A Prim algoritmusának futási ideje azonban Fibonacci-kupacok segítségével javítható. A Fibonacci-kupaccal megvalósított prioritásos sort használó Prim algoritmusának futási ideje $O(m + n \cdot log \space n)$.

Gyakorlati alkalmazása:

Városok közötti utak tervezésénél, elektromos hálózatok tervezésénél, számítógépes hálózatoknál használják.