Reprezentarea în memorie

1. Matricea de adiacență

  Matricea de adiacență este cea mai utilizată metodă de reprezentare a grafurilor orientate. Ea ne poate oferi mai multe informații utile despre graful reprezentat.
  Are următorul principiu de funcționare:

Matrice de adiacenta + Graf orientat

  Diferit față de matricea de adiacență a grafurilor neorientate, în aceasta vom pune valoarea 1 acolo unde linia este extremitatea inițială, iar coloana este extremitatea finală a fiecărui arc, pe rând.
  Exemplu de matrice de adiacență:

Graf orientat + Matrice de adiacenta

Proprietăți ale matricei de adiacență

  1. Diagonala principală are toate elementele egale cu 0;
  2. Suma elementelor din matrice este m (numărul total de arce ale grafului);
  3. Suma elementelor de pe o linie reprezintă gradul exterior al nodului cu indicele corespunzător.
  4. Suma elementelor de pe o coloană reprezintă gradul interior al nodului cu indicele corespunzător.

2. Liste de adiacență

  Lista de adiacență a unui nod i în graful orientat conține toate nodurile către care pleacă arce din i.
  Exemplul descrierii unei liste de adiacență:

Graf orientat + Lista de adiacenta

Proprietăți ale listelor de adiacență

  1. Numărul nodurilor din lista unui nod reprezintă gradul exterior al acestuia;
  2. Pentru fiecare nod, numărul de apariții în celelalte liste reprezintă gradul interior al acestuia;
  3. Numărul total de elemente din toate listele este egal cu m (numărul total de arce).