REPREZENTAREA GRAFURILOR NEORIENTATE

Listele de adiacenta a nodurilor

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 nodului 3: 2, 4, 5 (noduri adiacente)

Nodul 6 nu are vecini (este izolat)

Pentru intreg graful vom avea mai multe liste :

Nodul 1 :

Nodul 2 :

Nodul 3 :

Nodul 4 :

Nodul 5 :

Ordinea nodurilor 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 noduri si muchiile 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 vecinilor nodului nr_nod

{nod *p=L[nr_nod];

if(p==0)

cout<<nr_nod<<" este izolat "<<endl;

else

{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;

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

q->nd=i;

q->next=L[j];

L[j]=q;

}

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 muchii, atunci se va folosi matricea de adiacenta; daca numarul de muchii 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 neorientat utilizand liste de adiacente. Parcurgand listele de adiacenta rezolvati urmatoarele cerinte :

a. Sa se determine daca graful contine noduri izolate

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

c. Sa se determine nodul 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

g. Sa se genereze matricea de adiacenta a grafului

2. Sa se determine daca n liste citite de la tastatura pot reprezenta un graf. In caz afirmativ sa se afiseze muchiile.