Algoritmul lui Kruskaleste unalgoritmnteoria grafurilorcare gsetearboreleparial de cost minim pentru ungrafconexponderat. Cu alte cuvinte, gsete submulimea muchiilor care formeaz un arbore care include toate vrfurile i care este minimizat din punct de vedere al costului. Dac graful nu este conex, atunci algoritmul gsete opdure parial de cost minim(un arbore parial de cost minim pentru fiecare component conex). Algoritmul lui Kruskal este un exemplu dealgoritm greedy.Algoritmul funcioneaz n felul urmtor: creeaz o pdureF(o mulime de arbori), unde fiecare vrf din graf este un arbore separat creeaz o mulimeScare conine toate muchiile din graf att timp ctSeste nevid elimin o muchie de cost minim dinS dac acea muchie conecteaz doi arbori distinci, atunci adaug muchia n pdure, combinnd cei doi arbori ntr-unul singur altfel, ignor muchiaLa sfritul algoritmului, pdurea are doar o component care reprezint un arbore parial de cost minim al grafului.PSEUDOCOD: 1 funcia Kruskal(G) 2 pentru fiecare vrf v n G execut 3 Definete un grup elementar C(v) {v}. 4 Creeaz o coad cu prioriti Q care conine muchiile din G, avnd costul drept cheie. 5 Definete un arbore T //T va conine n final toate muchiile din APCM 6 // n este numrul total de vrfuri 7 ct timp T are mai puin de n-1 muchii execut 8 // muchia u,v este drumul minim de la u la v 9 (u,v) Q.eliminMin()10 Fie C(v) grupul care l conine pe v i C(u) grupul care l conine pe u.11 dac C(v) C(u) atunci12 Adaug muchia (v,u) la T.13 Unete C(v) i C(u) ntr-un grup, adic reuniune ntre C(v) i C(u).14 returneaz arborele T