REPREZENTAREA GRAFURILOR ORIENTATE

Listele de adiacenta

Reprezentarea in calculator a unui graf se poate face utilizand listele de adiacenta a varfurilor, adica pentru fiecare varf se alcatuieste lista varfurilor adiacente cu el.

Fie graful din figura urmatoare:

Lista vecinilor varfului 5: 3, 4 (noduri adiacente)

Pentru intreg graful vom avea mai multe liste :

Varful 1 :

Varful 2 :

Varful 3 :

Varful 4 :

Varful 5 :

Varful 6

Ordinea varfurilor in cadrul unei liste nu este importanta

Pentru a genera o astfel de lista vom defini tipul nod :

struct nod {int nd;
nod *next;};

Toate listele se vor memora utilizand un vector de liste :

nod *L[20];

Datele de intrare : numarul de varfuri si arcele se vor citi din fisier :

O solutie de implementare este urmatoarea :

#include<conio.h>

#include<fstream.h>

struct nod

{int nd;

nod *next;};

nod *L[20];

void afisare(int nr_nod) //afiseaza lista vecinilorvarfuluii nr_nod

{nod *p=L[nr_nod];

if(p!=0)

{cout<<"lista vecinilor lui "<<nr_nod<<endl;

nod *c=p;

while(c)

{cout<<c->nd<<" ";

c=c->next;}

cout<<endl;}

}

void main()

{fstream f;int i,j,n;

nod *p,*q;

f.open("graf.txt",ios::in); //citirea datelor din fisier

clrscr();

f>>n;

while(f>>i>>j)

{p=new nod; //se adauga j in lista vecinilor lui i

p->nd=j;

p->next=L[i];

L[i]=p;

}

f.close();

cout<<endl<<"listele de adiacente ";

for(i=1;i<=n;i++)

afisare(i);

getch();

}

Observatie : In exemplul anterior adaugarea unui nou element in lista se face inainte celorlalte din lista corespunzatoare.

Aceste doua moduri de reprezentare (prin matrice de adiacenta si prin liste de vecini) se folosesc dupa natura problemei. Adica, daca in problema se doreste un acces frecvent la arce, atunci se va folosi matricea de adiacenta; daca numarul de arce care se reprezinta este mult mai mic dect nxn, este de preferat sa se folosesca listele de adiacenta, pentru a se face economie de memorie.

Probleme propuse :

1. Sa se memoreze un graf orientat utilizand liste de adiacente. Parcurgand listele de adiacenta rezolvati urmatoarele cerinte :

a. Sa se determine daca graful contine varfuri izolate

b. Sa se determine gradul unui nod citit de la tastatura

c. Sa se determine varful cu cel mai mare grad

d. Sa se determine daca nodurile x si y sunt adiacente

e. Sa se verifice daca graful este regulat

f. Sa se determine daca graful este complet