Jarníkův algoritmus si udržuje jen jednu komponetu souvislosti a tu postupně rozšiřuje. Začne s komponentou souvislosti, která obsahuje jen počáteční vrchol $r$. V každém kroku tuto komponentu1 $T=(R,M)$ rozšíří o nejlevnější hranu řezu určeného touto komponentou.


Jarníkův/Primův algoritmus:

  1. $T:=(R,M)$, $R:=\{r\}$, $M:=\emptyset$.
  2. V každém kroku přidáme do $M$ nejlevnější hranu $e$ řezu $\delta(R)$ a do $R$ přidáme druhý konec hrany $e$ neležící v $R$.
  3. Po $n-1$ krocích se zastavíme, máme minimální kostru $T$.

Správnost algoritmu opět plyne z lemmat o meta-algoritmu a z faktu, že přidáváme nejlevnější hranu řezu určeného jedinou komponentou souvislosti $M$.

Implementace

Při realizaci algoritmu nemusíme probírat všechny hrany řezu. Pro každý vrchol, který ještě není v $R$, si budeme pamatovat hodnotu $\ARRAY{d}{v}=\,$nejmenší cena hrany vedoucí z $v$ do množiny $R$, a také $\ARRAY{odkud}{v}$ ta hrana vede. Na začátku bude hodnota všech $\ARRAY{d}{v}=\infty$, jen počáteční vrchol $r$ bude mít $\ARRAY{d}{r}=0$. Místo probírání všech hran řezu $\delta(R)$ stačí projít všechny hodnoty $\ARRAY{d}{v}$ a vybrat z nich tu nejmenší. Abychom v průběhu algoritmu udržovali obě pole aktuální, tak po každém přidání nového vrcholu do $R$ zkontrolujeme, jestli z něj nevede levnější hrana do vrcholů $V\setminus R$ a případně aktualizujeme hodnoty $\ARRAY{d}{v}$ a $\ARRAY{odkud}{v}$.

Jarník, Prim:
	 $\ARRAY{d}{r}:=0$ a $\forall\,v\in V\setminus\{r\}\,:\,\ARRAY{d}{v}:=\infty$
	 $\forall\,v\in V\,:\,\ARRAY{odkud}{v}:=nil$

	 vytvoř prioritní frontu $H$ z vrcholů $V$ s prioritami $\ARRAY{d}{v}$
	 while fronta $H$ neprázdná do
	 	 $v := \DELMIN(H)$
	 	 přidej hranu $\{v,\ARRAY{odkud}{v}\}$ do kostry
	 	 for each $vw\in E$ do
	 		 if $\ARRAY{d}{w}>c(vw)$ then
	 			 $\ARRAY{d}{w}:=c(vw)$
	 			 $\ARRAY{odkud}{w}:=v$
	 			 $\DECREASEKEY(H,w)$

Algoritmus je hodně podobný Dijkstrovu algoritmu pro hledání nejkratší cesty v grafu. Diskuse o možných realizacích prioritní fronty a jejich vhodnosti pro konkrétní grafy je naprosto stejná jako u Dijkstrova algoritmu. Proto zde uvedeme jen výsledky.

Časová složitost Jarníkova algoritmu při realizaci prioritní fronty v poli je $\OO(n^2+m)$. Při realizaci binární haldou je $\OO((n+m)\log n)$. Při použití $d$-regulární haldy s volbou $d\approx m/n$ (průměrný stupeň grafu) dostaneme pro velmi řídké grafy (tj. s $m=\OO(n)$) časovou složitost $\OO(n\log n)$ (stejně jako u binární haldy) a pro ostatní grafy lineární časovou složitost.

Příklad: Zkusme najít minimální kostru grafu, který je na následujícím obrázku vlevo, tentokráte ale podle Jarníkova algoritmu. Vrcholy i hrany grafu budeme procházet v abecedním pořadí. Jednotlivé kroky algoritmu jsou na obrázcích vpravo. Vrcholy patřící do množiny $R$ jsou na obrázcích zakroužkovány.

Jako počáteční vrchol si vybereme A. V prvním kroku mají všechny vrcholy až na A hodnotu $\ARRAY{d}{v}=\infty$. Proto si jako vrchol s nejmenší hodnotou $\ARRAY{d}{\cdot}$ vybereme vrchol A a přidáme ho do $R$. Při aktualizaci $\ARRAY{d}{\cdot}$ snížíme $\ARRAY{d}{B}=6$, $\ARRAY{d}{D}=4$, $\ARRAY{d}{E}=5$ a spolu s tím upravíme $\ARRAY{odkud}{\cdot}$. Ve druhém kroku si za vrchol s nejnižším $\ARRAY{d}{\cdot}$ vybereme vrchol D. Přidáme ho do $R$ a hranu $AD=\{D, \ARRAY{odkud}{D}\}$ přidáme do kostry. Dále postupujeme podobně, až dokud nedostaneme minimální kostru.