De ce contează?
Imaginează-ți un tabel „cine cu cine se cunoaște” într-o clasă: pe fiecare linie
și pe fiecare coloană scrii un elev, iar în căsuța de la intersecție bifezi 1
dacă cei doi sunt prieteni și 0 dacă nu. Ca să afli dacă Ana o cunoaște pe Dana
nu mai întrebi pe nimeni — te uiți direct în căsuța lor. Exact așa funcționează
matricea de adiacență a unui graf.
Ce este
Matricea de adiacență a unui graf cu n noduri este o matrice pătrată
a[n][n] în care fiecare celulă răspunde la o singură întrebare: „există
legătură directă între i și j?”
a[i][j] = 1dacă există muchie (la graf neorientat) sau arc (la graf orientat) de lailaj;a[i][j] = 0în caz contrar.
Imaginea mentală: toate legăturile grafului, întinse într-un tabel pătrat.
Întrebarea „e i vecin cu j?” nu mai cere nicio căutare — te duci pe linia
i, coloana j, și citești bifa.
Trei proprietăți de reținut:
- Graf neorientat → matrice simetrică. Muchia
i-jnu are sens de parcurs, deci o marchezi în ambele direcții:a[i][j] = a[j][i] = 1. - Graf orientat → matricea poate fi nesimetrică. Un arc
i → japrinde doara[i][j], nu șia[j][i]— ordinea indicilor contează. - Diagonala e
0la graful simplu. Fără bucle, niciun nod nu are muchie spre el însuși, decia[i][i] = 0pentru oricei.
La un graf neorientat, matricea se oglindește față de diagonala principală:
orice 1 de deasupra diagonalei are un geamăn dedesubt, în celula simetrică.
Dacă tabelul tău nu arată identic oglindit, ai uitat undeva jumătate dintr-o
muchie — iar DFS-ul și BFS-ul de mai târziu vor „vedea” un alt graf decât cel
citit.
Prețul acestei comodități se vede în costuri:
| Operație | Cost cu matrice |
|---|---|
„există muchie i-j?” | O(1) — o singură citire |
toți vecinii lui i | O(n) — parcurgi toată linia, chiar dacă are un singur 1 |
| memorie | O(n²) — indiferent câte muchii există de fapt |
Memoria O(n²) fixează limita practică: pe la n = 10^4 matricea atinge 10^8
celule și abia mai încape în limitele uzuale de concurs, iar peste — deloc. La
grafuri dense cu n mic, matricea e alegerea firească; la grafuri rare
cu n mare, rezervi milioane de căsuțe pentru câteva bife de 1 și treci la
liste de adiacență, care ocupă doar O(n + m).