De ce contează?
Ministerul scoate la licitație toate tronsoanele de cale ferată posibile din țară, într-un catalog sortat de la cel mai ieftin la cel mai scump. Tu cobori prin catalog rând cu rând: cumperi un tronson doar dacă leagă două orașe care încă NU comunică pe șine (nici direct, nici ocolit). Dacă între ele există deja drum, tronsonul e bani aruncați — îl sari. Pe hartă cresc simultan mai multe rețele mici care, tronson cu tronson, fuzionează într-una singură. Asta e algoritmul lui Kruskal: nu crește dintr-un punct, ca Prim — unește o pădure.
Intuiția
Știi deja de la lecția introductivă ce e un arbore parțial de cost minim (MST): muchii care leagă toate nodurile, fără cicluri, cu suma costurilor minimă. Kruskal îl construiește privind muchiile de la cea mai ieftină la cea mai scumpă: acceptă o muchie doar dacă unește două componente încă separate. O muchie între noduri deja conectate ar închide un ciclu — muchie în plus, cost în plus, niciun câștig.
De ce nu greșește niciodată lăcomia asta? Proprietatea tăieturii: oricum ai împărți nodurile în două grupuri, cea mai ieftină muchie care traversează împărțirea aparține sigur unui MST (dacă arborele ar folosi alta, mai scumpă, ai putea-o schimba cu cea ieftină și ai obține un arbore mai bun — contradicție). Fiecare muchie acceptată de Kruskal e exact muchia minimă dintre componenta ei și restul grafului, deci fiecare alegere e „sigură".