Reprezentarea în memorie

  Putem „ține minte în memorie” datele despre un graf neorientat în 4 moduri. Dintre acestea, matricea de adiacență este cea mai utilizată.

1. Șirul muchiilor

  Prin această modalitate vom ține minte toate muchiile într-un șir de date cu 2 câmpuri, construit în struct.

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

  Fiecare muchie memorată în tablou va avea 2 extremități corespunzătoare celor 2 câmpuri. Pentru o muchie i, ne vom referi la extremitățile ei prin U[i].x și U[i].y.


2. Matricea de adiacență

  Fiind și cea mai folosită metodă de reprezentare în memorie a grafurilor, matricea de adiacență ne va putea oferi mai multe informații despre graful nostru.   Principiul ei de funcționare este următorul:

Matrice de adiacenta

  Prin urmare, într-o matrice nulă vom pune 1 în pozițiile în care indicele liniei și coloanei sunt extremități ale unei muchii.

  Să vedem cum arată o matrice de adiacență:

Graf neorientat + Matrice de adiacenta

  Va avea atâtea linii și coloane câte noduri are graful, astfel că pentru graful din exemplu declararea matricei va fi: int A[6][6].
  Deoarece vom pune elementele începând cu linia și coloana 1, vom declara dimensiunile unei matrice ca fiind numărul de noduri + 1 (punându-le de la 1 ne deschide oportunitatea de a ține minte sume de pe linii și coloane în pozițiile 0 aferente).

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.

3. Matricea de incidență

  Mai puțin utilizată, matricea de incidență este asemănătoare cu cea de adiacență. Cu toate acestea, este mai costisitoare ca memorie și ne oferă mai puține informații decât cealaltă.
  Matricea va avea atâtea linii câte noduri are graful, iar atâtea coloane câte muchii are. Vom pune 1 pe coloane, în dreptul liniei corespunzătoare nodurilor ce sunt extremități.
  Urmează un exemplu grafic de matrice de incidență:

Graf neorientat + Matrice de incidenta

4. Liste de adiacență

  Lista de adiacență a unui nod i este formată din toate vârfurile adiacente cu i.
  Exemplul descrierii unei liste de adiacență:

Graf neorientat + Lista de adiacenta

Proprietăți ale listelor de adiacență

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