De ce contează?
Ai în față o foaie cu ofertele unei firme de drumuri: pe fiecare rând o lucrare — de unde pornește, unde ajunge și cât costă. Nu desenezi nicio hartă, nu grupezi nimic pe orașe: e doar o listă de rânduri, fiecare cu prețul lui. Dacă vrei să alegi lucrările de la cea mai ieftină la cea mai scumpă, sortezi foaia după ultima coloană și gata. Exact așa arată un graf ponderat ținut ca listă de muchii cu costuri — și exact așa începe Kruskal.
Ce este
Lista muchiilor cu costuri este lista muchiilor pe care o știi deja, cu un al
treilea câmp: costul. Fiecare muchie devine un triplet (u, v, cost):
u— un capăt al muchiei,v— celălalt capăt,cost— ponderea muchiei (lungime, preț, capacitate...).
Un graf cu n noduri și m muchii se reține ca un vector de m triplete —
memorie O(m), exact câte muchii există și nimic în plus. Spre deosebire de
matricea de costuri, care ocupă O(n²) chiar și pentru un graf rar, lista
muchiilor crește doar cu graful.
E și formatul în care problemele ponderate îți dau graful: pe prima linie
n și m, apoi m linii cu câte trei numere u v cost. Cu alte cuvinte,
lista muchiilor cu costuri se citește direct din fișier, fără nicio prelucrare.