Reprezentarea în memorie

Memorarea unui graf neorientat se face în general în 4 moduri. Dintre acestea, matricea de adiacență și listele de adiacență sunt cele mai utilizate.

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

Interpretând, într-o matrice cu n linii și n coloane, vom avea 1 acolo unde avem muchie între nodurile corespondente liniei și coloanei.

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

Matricea este Matricea pătratică este o matrice cu număr egal de linii și coloane.pătratică și are atâtea linii și coloane câte noduri are graful.

Implementarea acestei matrice de adiacență în C++ se poate face în felul următor:

int A[6][6]; //matricea de adiacenta
for(int i=1; i<=5; i++)
  for(int 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 și se poate face în mai multe moduri.

Proprietăți ale matricei de adiacență

1. Este simetrică în raport cu diagonala principală (încercuită în figură);
2. Diagonala principală are toate elementele egale cu 0;
3. Suma elementelor din matrice este 2*m (dublul numărului de muchii);
4. 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 liste de adiacență pentru un graf neorientat:

Proprietăți ale listelor de adiacență

1. Gradul unui nod este dat de numărul de elemente din lista lui de adiacență;
2. Numărul total de elemente din toate listele este egal cu 2*m (dublul numărului de muchii).

O matrice de incidență va lua pe coloane fiecare muchie în parte și va pune 1 pe liniile corespunzătoare nodurilor ce îi sunt extremități.
Ea este rar utilizată, deoarece este mai costisiotoare din punct de vedere al memoriei necesare față de alte metode de reprezentare.

Exemplu de matrice de incidență pentru un graf neorientat:

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

Proprietăți ale matricei de incidență:

1. Gradul unui nod este egal cu numărul de valori 1 de pe linia corespunzătoare acestuia;
2. Orice coloană are exact 2 valori de 1, reprezentând extremitățile muchiei respective;
3. Ordinea alegerii (numerotarea) muchiilor este arbitrară.

Șirul muchiilor unui graf neorientat poate fi memorat și cu ajutorul unei structuri (Structură ce grupează mai multe valori (câmpuri) asociate unei variabile.struct).

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

În tabloul U pot fi memorate muchii. Pentru o muchie i, ne vom referi la extremitățile ei prin U[i].x și U[i].y.