Reprezentarea în memorie

Memorarea unui graf neorientat se face de cele mai multe ori fie printr-o matrice de adiacență, fie prin liste de adiacență. Bineînțeles, există și alte metode mai puțin folosite, dintre care am prezentat două. Astfel, iată 4 tipuri de memorare a grafurilor neorientate:

Cea mai folosită metodă de reprezentare în memorie a grafurilor neorientate, matricea de adiacență are în spate un principiu simplu. Se definește ca:

Interpretarea definiției este aceea că într-o matrice cu $n$ linii și $n$ coloane, vom avea valoarea 1 acolo unde avem o muchie între nodurile corespunzătoare indexului liniei și a coloanei.

Exemplul unei matrice de adiacență pentru un graf neorientat:

Matricea este pătratică și are atâtea linii și coloane câte noduri are graful.

Implementarea în C++

Un model de implementare a matricelor de adiacență poate fi următorul:

int A[6][6], i, j;
for(i = 1; i <= 5; i++) {
    for(j = 1; j <= 5; j++) {
        if(/* exista muchie intre i si j */)
            A[i][j] = 1;
        else
            A[i][j] = 0;
    }
}

Declararea efectivă este o simplă inițializare de matrice cu 6 linii și 6 coloane (considerăm indexare de la 1, acomodează deci 5 noduri). Popularea cu valori de $0$ și $1$ se face în funcție de existența muchiei între nodurile corespunzătoare liniei și coloanei.

Proprietăți ale matricei de adiacență

• este simetrică în raport cu diagonala principală (încercuită în figură);
• diagonala principală are toate elementele egale cu $0$;
• suma elementelor din matrice este $2*m$ (dublul numărului de muchii);
• suma elementelor de pe o linie/coloană reprezintă gradul nodului cu indicele corespunzător.

Listele de adiacență ale unui graf neorientat sunt o colecție de liste specifice fiecărui nod din graf și conțin toți vecinii acestora. Prin urmare, lista de adiacență a unui nod $i$ este formată din toate vârfurile adiacente cu $i$.

Exemplu de liste de adiacență pentru un graf neorientat:

Implementarea în C++

Implementarea listelor de adiacență în C++ pentru graful de mai sus se poate face, de exemplu, tot cu tablouri:

int L[11][11], G[11], i, j;
for(i = 1; i < 10; i++) {
    for(j = i + 1; j <= 10; j++) {
        if(/* exista muchie intre i si j */) {
            L[i][G[i]++] = j;
            L[j][G[j]++] = i;
        }
    }
}

Aici, pentru fiecare linie din matrice, care corespunde câte unui nod, memorăm nodurile adiacente cu acesta. Acest exemplu de implementare este doar o variantă posibilă, existând și altele mult mai eficiente ca memorie utilizată.

Proprietățile listelor de adiacență

• gradul unui nod este dat de numărul de elemente din lista sa de adiacență;
• numărul total de elemente din toate listele este egal cu $2*m$ (dublul numărului total de muchii).

O matrice de incidență asociază fiecărei muchie din graf o coloană, având cifra $1$ pe liniile corespunzătoare nodurilor extremități.

Iată un exemplu de matrice de incidență pentru un graf neorientat:

Matricea are atâtea linii câte noduri și atâtea coloane câte muchii are graful.

Mult mai costisitoare din punct de vedere al memoriei utilizate, matricea de incidență a grafurilor neorientate este mult mai rar folosită față de alte metode de reprezentare.

În plus, construirea unei astfel de matrice depinde de contextul în care putem parcurge muchiile, construirea efectivă având mai multe variante.

Proprietăți ale matricei de incidență

• gradul unui nod este egal cu numărul de valori $1$ de pe linia corespunzătoare acestuia;
• orice coloană are exact 2 valori de $1$, reprezentând extremitățile muchiei respective;
• ordinea alegerii (numerotarea) muchiilor este arbitrară, astfel că matricea nu are o formă fixă.

Mai putem memora un graf neorientat folosind șiruri de muchii. Cu un principiu asemănător matricei de incidență, ideea este de a memora toate muchiile grafului într-un șir.

Putem implementa un astfel de șir de muchii folosind structuri (struct).

struct muchie {
    int x, y;
} U[101];

// accesarea extremitatilor unei muchii
cout << "Prima muchie: [" << U[0].x << "," << U[0].y << "].";