De ce contează?
Ai în telefon o agendă cu prietenii tăi. Până acum rețineai doar cine îți este prieten. Acum, lângă fiecare nume, mai notezi și un număr: câți kilometri ai de mers până la el. Fișa ta nu mai conține doar „Ana, Bogdan, Carla", ci „Ana — 4 km, Bogdan — 3 km, Carla — 7 km". Exact așa stochează un calculator un graf în care muchiile au costuri: pentru fiecare nod, o listă de vecini, dar fiecare vecin vine la pachet cu costul drumului până la el.
Ce este
La un graf simplu, lista nodului 1 îți spunea doar cu cine e vecin. Dar multe
probleme reale au muchii cu pondere: distanțe între orașe, costul unui zbor,
timpul pe o șosea. Acum nu mai e suficient să știi că de la 1 ajungi la 2 —
trebuie să știi și cât te costă.
O listă de adiacență cu costuri este o listă de adiacență obișnuită în care
fiecare intrare nu mai e un singur număr (vecinul), ci o pereche (vecin, cost).
Pentru fiecare nod u, ții lista tuturor perechilor (v, c) pentru care există
muchia u-v de cost c. În C++ forma standard este un vector de perechi pentru
fiecare nod: vector<pair<int,int>> adj[N], unde adj[u] conține perechi
{vecin, cost}.
Costul este lipit de muchie, nu de nod: când călătorești, mergi pe o muchie
și plătești costul ei. De aceea costul stă în listă chiar lângă vecin — perechea
(v, c) din adj[u] înseamnă „muchia de la u la v costă c". La graf
neorientat, aceeași muchie apare în două liste, cu același cost în ambele:
drumul costă la fel indiferent din ce capăt îl privești.
Două proprietăți moștenite direct de la lista de adiacență simplă:
- Memorie O(n+m): ai aceleași intrări ca la lista simplă (
2mla neorientat,mla orientat), doar că fiecare intrare e o pereche în loc de un întreg. Costul pe muchie e o constantă, deci ordinul de mărime al memoriei nu se schimbă. La grafuri rare rămâne mult sub matricea costurilor, care ar plăti O(n^2) memorie ca să țină și căsuțele goale. - Parcurgerea în O(grad): ca să treci prin vecinii lui
uși costurile lor, parcurgi listaadj[u]și citești din fiecare pereche atât vecinul, cât și costul — un singur pas pe vecin.
Aceasta este reprezentarea standard pentru algoritmii pe grafuri ponderate: Dijkstra cu heap (drumuri minime) și Prim (arbore parțial de cost minim) au nevoie exact de „pentru fiecare nod, lista vecinilor cu costuri", parcursă în O(grad).