Reprezentarea grafurilor in memorie


1.Matricea de adiacenta asciatã unui graf neorientat cu n noduri se defineste astfel: A = (aij) cu aij = este 0, daca nu exista muchie intre noduil i si nodul j si este 1 daca exista muchie intre i si j


Observatii:

  • Diagonala principala a matricei de adiacenta este tot timpul 0
  • Matricea de adiacenta este simetrica fata de diagonala principala



2.Matricea de incidenta are n linii(n=nr de noduri) si m coloane(m=nr de muchii). Pe fiecare coloana exista 2 valori de 1 care reprezinta extremitatea unei muchii, toate celelalte sunt 0.




3.Lista muchiilor

Aceasta lista e reprezentata in memorie cu un vector cu m elemente de tip struct.

Ex: { {(1,2);(1,4);(2,5);(2,6);(3,4);(3,6)}

4.Lista vecinilor

Se scriu nodurile 1:2,4

2:5,6

3:4,6

4:1,3

5:2

6:2,3


Category: 0 comentarii

Niciun comentariu:

Trimiteți un comentariu