Reprezentarea grafurilor

Matricea de adiacență, listele de vecini și lista de muchii: ce afli ușor din fiecare și câtă memorie cer.

Problema

Un graf trebuie pus într-o formă pe care programul o poate citi. Ai trei variante, iar de alegerea făcută depinde cât de ușor răspunzi la fiecare întrebare.

Ca exemplu folosim graful cu 5 vârfuri și muchiile [1,2], [1,3], [2,3], [4,5].

Matricea de adiacență

O matrice n × n de zerouri și unu:

a[i][j] = 1  dacă există muchia [i, j]
a[i][j] = 0  altfel

Pentru exemplul nostru:

Așa se citește:

int a[101][101], n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    a[x][y] = 1;
    a[y][x] = 1;        // graf neorientat: ambele sensuri
}

A doua atribuire este obligatorie la grafuri neorientate. Dacă o uiți, graful devine orientat fără niciun mesaj de eroare. Este cea mai frecventă greșeală de la acest capitol.

Proprietăți utile:

• Matricea este simetrică față de diagonala principală.
• Diagonala principală este 0 (dacă nu există bucle).
• Gradul vârfului i = suma de pe linia i:

int grad = 0;
for (int j = 1; j <= n; j++)
    grad += a[i][j];

• Numărul de muchii = suma tuturor elementelor, împărțită la 2.

Avantajul: afli instantaneu dacă două vârfuri sunt vecine, dintr-o singură citire: a[x][y].

Dezavantajul: ocupă n² memorie indiferent de câte muchii sunt. Ca să afli vecinii unui vârf, trebuie să parcurgi toată linia. Pentru n = 10000, matricea are 100 de milioane de elemente, adică prea mult.

La bac, unde n este de obicei sub 100, matricea de adiacență este alegerea normală.

Listele de vecini

Pentru fiecare vârf, lista vârfurilor cu care este legat:

1: 2, 3
2: 1, 3
3: 1, 2
4: 5
5: 4

Fără STL, care nu intră în programă, se ține într-o matrice plus un vector de lungimi:

int vecin[101][101], nrv[101];

for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    vecin[x][++nrv[x]] = y;
    vecin[y][++nrv[y]] = x;
}

nrv[x] este chiar gradul lui x, gata calculat.

Parcurgerea vecinilor unui vârf devine directă:

for (int i = 1; i <= nrv[x]; i++) {
    int y = vecin[x][i];
    // y este vecin cu x
}

Avantajul: parcurgi doar vecinii care există, nu toate cele n posibilități. La grafurile cu puține muchii, asta e mult mai rapid.

Dezavantajul: ca să afli dacă x și y sunt vecine, trebuie să cauți în listă.

Lista de muchii

Păstrezi pur și simplu perechile, într-un vector de structuri:

struct Muchie { int x, y; };
Muchie e[1001];

Așa vin de obicei datele în fișier. Rar lucrezi direct pe această formă, dar e utilă când trebuie să sortezi muchiile sau doar să le parcurgi pe toate.

Cum alegi

La examen, cu n mic, matricea de adiacență este de obicei cea mai simplă și cea mai puțin predispusă la greșeli.

Cazuri de care să ții cont la citire

Muchii duplicate. Dacă fișierul conține [1,2] de două ori, matricea nu se schimbă (rămâne 1), dar lista de vecini îl adaugă de două ori și gradul iese greșit.

Bucle ([3,3]). În matrice, a[3][3] = 1. De obicei se consideră că o buclă adaugă 2 la grad, deci aici gradul nu mai e suma liniei. Grafurile de la bacalaureat nu au bucle, așa că nu vei întâlni cazul la examen.

Dacă enunțul nu le exclude explicit, gândește-te și la ele.

De reținut

• Matrice de adiacență: a[x][y] = a[y][x] = 1, ambele, la graf neorientat.
• Matricea unui graf neorientat este simetrică. Gradul este suma liniei.
• Listele de vecini economisesc memorie și timp când muchiile sunt puține.
• Numărul de muchii = suma tuturor elementelor matricei, împărțită la 2.
• La bac, cu n mic, matricea de adiacență e alegerea sigură.