Kruskalův algoritmus je nejjednoduší implementací meta-algoritmu. Zjenodušil si práci s výběrem nejlevnější hrany řezu tím, že prochází hrany v pořadí podle jejich velikosti. Každou procházenou hranu zkusí přidat do kostry. Pokud hrana $e=uv$ spojuje různé komponenty souvislosti množiny $M$, tak přidá hranu $e$ do kostry. Aniž to algoritmus tuší, nalezl zároveň i vhodný řez pro meta-algoritmus. Je to řez určený komponentou souvislosti $C_u$ nebo $C_v$, kde $C_v$ značí komponentu souvislosti obsahující vrchol $v$. Hrana $e$ je zaručeně nejlevnější hranou řezu $\delta(C_v)$, protože hrany procházíme podle velikosti a všechny menší hrany už leží uvnitř komponent souvislosti $M$. Správnost Kruskalova algoritmu plyne z předchozích lemmat meta-algoritmu.


Kruskalův hladový algoritmus:

  1. Seřaď hrany podle velikosti $e_1 \leq e_2 \leq \dots \leq e_m$.
  2. $M:=\emptyset$. Procházej hrany v pořadí podle velikosti. Pokud hrana $e_i$ spojuje různé komponenty souvislosti $M$, tak ji přidej do $M$ a sjednoť příslušné komponenty souvislosti.
  3. Na konci je $M$ minimální kostra.

Algoritmus na začátku třídí $m$ hran, což mu trvá $\OO(m \log m)$. Zjišťování, jestli dva vrcholy patří do stejné komponenty souvislosti, případně sjednocení komponent, není nic jiného než Union-Find problém. Proto v bodě 2 provede algoritmus $m$-krát operaci $\FIND{}$ a $(n-1)$-krát operaci $\UNION$. To mu zabere čas $\OO((m+n)\log n)$. Operace $\UNION{}$ a $\FIND{}$ umíme realizovat i tak, aby druhá fáze trvala jen čas $\OO((m+n)\alpha(n))$, kde $\alpha(n)$ je inverzní Ackermanova funkce. Ale díky časové složitosti první fáze to není potřeba, celkovou časovou složitost algoritmu $\OO(m \log n)$ to nezmenší.1

Pokud dostaneme hrany už v setříděném pořadí, tak je časová složitost jenom $\OO((m+n)\alpha(n))$. Tedy prakticky lineální ve velikosti grafu.

Příklad: Na následujícím obrázku vlevo je ohodnocený graf, ve kterém chceme najít minimální kostru.

Hrany si seřadíme podle velikosti a dostaneme pořadí BE, BD, DE, BC, AD, CE, AE, CF, AB, BF, EF.2 V tomto pořadí hrany probíráme a zkoušíme je přidat do kostry. Pokud by přidáním hrany vznikla kružnice, tak ji nepřidáme. Průběh algoritmu je zachycen na obrázcích vpravo.