Reprezentarea grafurilor

Un graf poate fi păstrat ca listă de muchii, matrice de adiacență sau liste de adiacență. Pentru graful neorientat cu muchiile $\{1,2\}$ și $\{2,3\}$, lista de vecini a lui 2 este $[1,3]$. În matrice, pozițiile $(1,2)$, $(2,1)$, $(2,3)$ și $(3,2)$ sunt marcate.

Un graf cu $n$ vârfuri și $m$ muchii (sau arce) poate fi memorat în trei moduri uzuale. Matricea de adiacență are $n\times n$ elemente și a[i][j]=1 dacă există muchia sau arcul de la $i$ la $j$. Listele de adiacență păstrează, pentru fiecare vârf, lista vecinilor lui. Lista muchiilor (sau a arcelor) păstrează perechile de extremități. Alegerea depinde de operația frecventă și de cât de multe muchii are graful.

Exemplul 1 — matricea de adiacență. Pentru muchiile $\{1,2\}$ și $\{2,3\}$:

#include <iostream>
using namespace std;
int main() {
    int a[4][4] = {};
    a[1][2] = a[2][1] = 1;
    a[2][3] = a[3][2] = 1;
    cout << a[1][3] << " " << a[2][3];
}

Se afișează 0 1: nu există muchie directă 1–3, dar există 2–3. Matricea folosește spațiu proporțional cu $n^2$ și testează o muchie direct, în timp constant. Listele de vecini folosesc spațiu proporțional cu $n+m$, fiind convenabile pentru grafuri rare, adică cu puține muchii. Dacă a[1][3]=0, lipsește muchia $[1,3]$, dar există lanțul 1–2–3.

Exemplul 2 — de la matrice la celelalte reprezentări. Graful neorientat are 4 vârfuri și muchiile $[1,2]$, $[2,3]$, $[2,4]$. Programul pornește de la matrice, extrage lista muchiilor (numai perechile $i<j$, ca fiecare muchie să apară o singură dată) și listele de adiacență:

#include <iostream>
using namespace std;
int main() {
    int n = 4, a[5][5] = {};
    a[1][2] = a[2][1] = a[2][3] = a[3][2] = a[2][4] = a[4][2] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i][j]) cout << i << " " << j << "\n";
    for (int i = 1; i <= n; ++i) {
        cout << i << ":";
        for (int j = 1; j <= n; ++j)
            if (a[i][j]) cout << " " << j;
        cout << "\n";
    }
}

Se afișează lista muchiilor 1 2, 2 3, 2 4, apoi listele 1: 2, 2: 1 3 4, 3: 2 și 4: 2. Lista muchiilor păstrează fiecare muchie o singură dată într-un graf neorientat, dar căutarea tuturor vecinilor unui vârf cere parcurgerea întregii liste, dacă nu există un index separat. În listele de adiacență, fiecare muchie apare în două liste, deci în total sunt $2m=6$ elemente. Pentru un graf orientat, lista conține arce, iar sensul fiecăruia contează: arcul $(1,2)$ apare în lista lui 1, nu și în a lui 2.

Alegerea reprezentării. Dacă programul întreabă des „există muchia $[x,y]$?”, matricea răspunde în $O(1)$, iar listele cer parcurgerea listei lui $x$. Dacă programul parcurge vecinii unui vârf, cum fac parcurgerile în lățime și în adâncime, listele examinează numai vecinii existenți, adică $O(n+m)$ în total, în timp ce matricea examinează o linie întreagă pentru fiecare vârf, adică $O(n^2)$. Pentru un graf rar cu $n=1000$ și $m=2000$, o parcurgere pe matrice verifică un milion de celule, iar pe liste cel mult $n+2m=5000$ elemente. Pentru un graf aproape complet, diferența dispare, iar matricea este mai simplă.

Exemplul 3 — graf orientat. Un graf orientat cu 3 vârfuri are arcele $(1,2)$, $(2,3)$, $(3,1)$ și $(1,3)$. Matricea de adiacență nu este simetrică: liniile sunt 011, 001 și 100. Sumele liniilor sunt 2, 1 și 1, adică gradele externe ale vârfurilor (numărul arcelor care pleacă din vârf). Sumele coloanelor sunt 1, 1 și 2, adică gradele interne (numărul arcelor care intră). Ambele însumează 4, numărul arcelor, iar listele de adiacență sunt 1: 2 3, 2: 3 și 3: 1.

int n = 3, m = 4, a[4][4] = {};
int arce[4][2] = {{1, 2}, {2, 3}, {3, 1}, {1, 3}};
for (int k = 0; k < m; ++k)
    a[arce[k][0]][arce[k][1]] = 1;
for (int i = 1; i <= n; ++i) {
    int ext = 0, in = 0;
    for (int j = 1; j <= n; ++j) {
        ext += a[i][j];
        in += a[j][i];
    }
    cout << ext << in << ' ';
}

Programul afișează 21 11 12 , adică perechile (grad extern, grad intern) ale vârfurilor 1, 2 și 3. Pentru un graf orientat fiecare arc se marchează o singură dată în matrice, deci diferă de cazul neorientat, în care marcarea se face în ambele celule simetrice.

Într-un graf neorientat simplu, matricea este simetrică și diagonala este zero. Suma valorilor ei este $2m$, nu $m$, fiindcă fiecare muchie apare în două celule. Suma elementelor de pe linia $i$ este gradul vârfului $i$. Într-un graf orientat, doar celula corespunzătoare sensului arcului este marcată, iar suma tuturor elementelor este $m$, numărul arcelor. Pentru graful neorientat, lungimea totală a listelor de adiacență este tot $2m$, iar lista muchiilor are $m$ perechi. Matricea ocupă $n^2$ celule indiferent de $m$; pentru $n=1000$ și $m=2000$ ea are un milion de celule, față de $2m=4000$ elemente în listele de adiacență. Dacă un enunț dă matricea, gradele se citesc din sumele liniilor; dacă dă listele, din lungimile lor.

Exemplu în formatul examenului. Un graf neorientat simplu are matricea de adiacență cu suma tuturor elementelor egală cu 14. Câte muchii are graful?

• a) 7
• b) 14
• c) 28
• d) 49

Răspunsul corect este a). Fiecare muchie $[i,j]$ marchează două celule, a[i][j] și a[j][i], deci suma elementelor este $2m$ și $m=14/2=7$. Varianta b) confundă suma cu numărul muchiilor, iar varianta c) dublează suma în loc să o înjumătățească. Varianta d) este $7^2$, fără legătură cu datele. Același graf are 14 elemente în listele de adiacență, adică suma gradelor, și 7 perechi în lista muchiilor.

Greșeli frecvente

• Greșit: marcarea lui a[1][2] este suficientă pentru o matrice de graf neorientat.
  Corect: marchează și a[2][1].
• Greșit: suma matricei este numărul muchiilor neorientate.
  Corect: este dublul lui pentru graf simplu.
• Greșit: matricea arată un drum 1–3 dacă a[1][3]=0.
  Corect: acea celulă arată doar adiacența directă.

Înainte și după