Algoritmul Kruskal

Strategia folosită este una greedy, cu o idee foarte simplă: se ordonează muchiile după cost, apoi se parcurg crescător iar muchia curentă se alege dacă și numai dacă extremitățile ei sunt în acel moment în componente conexe diferite. Pentru a ține evidența componentelor conexe în mod dinamic se folosesc păduri de mulțimi disjuncte.