De ce contează?
La finalul unei etape de campionat, federația nu păstrează o schemă cu toate echipele și relațiile dintre ele. Păstrează procesul-verbal: lista partidelor jucate — „Rapid – Dinamo", „Steaua – Craiova", „Rapid – Craiova". Atât. Nu grupează nimic pe echipe, nu desenează nimic — doar înșiră meciurile, unul sub altul. Asta e lista muchiilor unui graf: un simplu tabel de perechi „cine e legat cu cine".
Ce este
Lista muchiilor stochează un graf ca un vector cu toate muchiile: fiecare
element e o pereche (u, v) — sau un triplet (u, v, cost) la grafuri
ponderate. Pentru un graf cu m muchii, vectorul are exact m elemente.
Imaginea mentală: o singură coloană de perechi, în ordinea citirii — nicio
grupare pe noduri, niciun tabel n x n.
Consecințele acestei alegeri:
- Memorie O(m) — reții fix o pereche per muchie, indiferent câte noduri are graful. Pentru grafuri rare e cea mai compactă reprezentare posibilă.
- Fără test rapid de adiacență — ca să afli dacă există muchia
(x, y), parcurgi toată lista: O(m) pentru o singură întrebare. - Fără acces rapid la vecini — „toți vecinii lui
x" înseamnă tot o parcurgere completă a listei. Nu poți „sări" direct la legăturile unui nod.
Lista muchiilor e formatul natural al inputului. Aproape orice problemă de
graf îți dă datele exact așa: pe prima linie n și m, apoi m linii cu câte
o pereche u v. Deci nu te întrebi „folosesc lista muchiilor?" — o ai deja în
mână în momentul citirii. Întrebarea reală e: o păstrezi așa sau o
transformi (de regulă în liste de adiacență)?