De ce contează?
Gândește-te la agenda de contacte din telefon. Nu ții o tablă uriașă cu toți oamenii din lume pe linii și coloane, bifând cine cunoaște pe cine. Pentru fiecare persoană ții doar o listă scurtă: prietenii ei direcți. Vrei să vezi cu cine vorbește Ana? Deschizi fișa Anei și citești exact prietenii ei, nimic în plus. Exact așa stochează un calculator un graf prin liste de adiacență.
Ce este
O listă de adiacență este o colecție de liste: pentru fiecare nod ții o
listă cu toți vecinii lui direcți. Lista nodului u conține fix nodurile la
care u are muchie — și atât. În loc să rezervi o tablă n x n în care
majoritatea căsuțelor spun „nu există muchie", plătești memorie doar pentru
muchiile care chiar există.
În C++ vei întâlni două forme echivalente:
vector<vector<int>> adj(n + 1);— dimensionat exact după ce citeștin(forma recomandată);vector<int> adj[N];— tablou global de vectori, cuNo constantă acoperitoare (de exemplu100005).
În ambele, adj[u] este lista vecinilor nodului u. Costurile care contează:
- Memorie
O(n+m): ainliste plus, în total, exact atâtea intrări câte capete de muchie există —2mla graf neorientat (fiecare muchie apare în două liste),mla orientat. - Parcurgerea vecinilor lui
uînO(grad(u)): treci doar prin listaadj[u], deci faci atâția pași câți vecini are nodul — nunpași, ca la o linie de matrice.
Pune numere de concurs pe ambele: la n = 10^5 noduri și m = 2 * 10^5
muchii, o matrice de adiacență ar avea 10^10 căsuțe — în jur de 10 GB,
programul moare înainte să înceapă. Listele țin 2m = 4 * 10^5 numere
întregi, adică vreo 1,6 MB. Aceeași informație, de un milion de ori mai
puțină memorie.
Insight-ul central: memoria listelor urmează muchiile reale ale grafului,
nu toate perechile posibile de noduri — de aceea O(n+m), nu O(n^2).
Cum majoritatea grafurilor din probleme sunt rare (au mult mai puține
muchii decât n^2), listele de adiacență sunt reprezentarea standard
pentru BFS și DFS: o parcurgere vizitează fiecare listă exact o dată, deci
totalul este O(n+m).