De ce contează?
Imaginează-ți aceeași rețea de drumuri dintre orașe, dar notată în trei feluri. Poți face un tabel mare în care căsuța (oraș A, oraș B) e bifată dacă există drum direct. Poți face în schimb, pentru fiecare oraș, o listă cu vecinii lui imediați. Sau poți scrie pur și simplu un catalog de drumuri: „de la A la B”, „de la C la D”. Harta e aceeași — orașele și drumurile nu se schimbă. Ce se schimbă e cât de repede răspunzi la întrebări diferite. Alegi notarea după ce vrei să faci cu harta.
Ideea-cheie
Ai învățat deja cele trei reprezentări ale unui graf: matricea de adiacență, listele de adiacență și lista muchiilor. Toate trei descriu exact același graf — aceleași noduri, aceleași muchii. Niciuna nu e „mai corectă” decât celelalte.
Diferența e una singură: fiecare reprezentare face alte operații rapide și
ocupă altă cantitate de memorie. Matricea răspunde instant la „există muchia
între i și j?”, dar mănâncă O(n^2) memorie. Listele îți dau vecinii unui nod
imediat și ocupă doar O(n + m). Lista muchiilor e ideală când vrei să te plimbi
prin toate muchiile sau să le sortezi, dar nu știe repede cine sunt vecinii unui nod.
Reprezentarea NU schimbă graful — schimbă doar ce operații sunt ieftine. De aceea
nu alegi „cea mai bună” reprezentare în abstract; o alegi după ce te întreabă
problema și după mărimile n (noduri) și m (muchii). Întâi citește ce operație
se repetă des în algoritmul tău, apoi alege structura care o face rapidă.