Grafuri neorientate

Algoritmul de parcurgere in latime

 

 

 

Se va folosi o coada  in care se inscriu nodurile in forma in care sunt parcurse: nodul initial varf (de la care se porneste), apoi nodurile a,b,…, adiacente lui varf, apoi cele adiacente lui a, cele adiacente lui b,… ,s.a.m.d.

 

Coada este folosita astfel:

 

– se pune primul nod in coada;

– se afla toate varfurile adiacente cu primul nod si se introduc dupa primul nod

– se ia urmatorul nod si i se afla nodurile adiacente

– procesul se repeta pana cand se ajunge la sfarsitul cozii

 

-Graful se va memora utilizand matricea de adiacenta a[10][10]

 

– Pentru memorarea succesiunii nodurilor parcurse se va folosi un vector c[20] care va functiona ca o coada

 

– Pentru a nu parcurge un nod de doua ori se va folosi un vector boolean viz[20] care va retine :

 

– viz[k]=0 daca nodul k nu a fost vizitat inca

 

– viz[k]=1 daca nodul k a fost vizitat

 

– Doua variabile : prim si ultim vor retine doua pozitii din vectorul c si anume :

 

– prim este indicele componentei pentru care se parcurg vecinii (indexul componentelor marcate cu rosu in sirurile parcurse anterior ). Prin urmare Varf=c[prim], este elementul pentru care se determina vecinii (nodurile adiacente)

 

-ultim este pozitia in vector pe care se va face o noua inserare in vectorul c (evident, de fiecare data cand se realizeaza o noua inserare se mareste vectorul)

 

-Vecinii nodului varf se « cauta » pe linia acestui varf : daca a[varf][k]=1 inseamna ca nodurile varf si k sunt adiacente. Pentru ca nodul k sa fie adaugat in coada trebuie ca nodul sa nu fi fost vizitat : viz[k]=0

 

#include<fstream.h>

 

#include<conio.h>

 

int a[10][10],c[20],viz[10];

 

int n,m,prim,ultim,varf;

 

void bf_iterativ() //parcurgerea in latime

 

{int k;

 

while(prim<=ultim)

 

{varf=c[prim];

 

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

 

if(a[varf][k]==1&&viz[k]==0) //il adaug pe k in coada daca este vecin pt. varf si nu a fost vizitat

 

{ultim++;

 

c[ultim]=k;

 

viz[k]=1;}

 

prim++;

 

}

 

}

 

void main()

 

{clrscr();

 

int x,y;

 

fstream f; //memorare graf in matrice de adiacenta

 

f.open(“muchii.txt”,ios::in);

 

f>>n>>m;

 

for(int i=1;i<=m;i++)

 

{f>>x>>y;

 

a[x][y]=a[y][x]=1;

 

}

 

cout<<“matricea de adiac “<<endl; // afisare matrice de adiacenta

 

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

 

{for(int j=1;j<=n;j++)

 

cout<<a[i][j]<<” “;

 

cout<<endl;

 

}

 

int nd;

 

prim=ultim=1;

 

cout<<“nodul de inceput=”;

 

cin>>nd;  // nodul de la care se porneste parcurgerea

 

viz[nd]=1;

 

c[prim]=nd;

 

bf_iterativ();

 

for(i=1;i<=ultim;i++)   //afisarea cozii

 

cout<<c[i]<<” “;

 

getch();

 

}

 

Varianta recursiva de parcurgere se obtine modificand functia de parcurgere iterativa adaugand conditia necesara autoapelului:

 

void bf_recursiv() //parcurgerea in latime

 

{int k;

 

if(prim<=ultim)

 

{varf=c[prim];

 

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

 

if(a[varf][k]==1&&viz[k]==0) //il adaug pe k in coada daca este vecin pt. varf si nu a fost vizitat

 

{ultim++;

 

c[ultim]=k;

 

viz[k]=1;}

 

prim++;

 

bf_recursiv();

 

}

 

}

 

Parcurgerea in latime a grafurilor memorate prin liste este similara cu diferenta cavecinii unui nod adaugat in coada se cauta in lista corespunzatoare lui :

 

#include<conio.h>

 

#include<fstream.h>

 

struct nod

 

{int nd;

 

nod *next;};

 

nod *L[20];

 

int viz[100]; //marchez cu 1 nodurile vizitate

 

int m,n;

 

int prim,ultim,C[100];

 

void bfi_lis()

 

{int varf,nr;

 

nod *p;

 

while(prim<=ultim)

 

{varf=C[prim];

 

p=L[varf]; // se parcurge lista elementelor din varful cozii

 

while(p)

 

{nr=p->nd;

 

if(viz[nr]==0) //numai daca nu a fost vizitat

 

{ultim++; //maresc coada

 

C[ultim]=nr; //il adaug in coada

 

viz[nr]=1;};  //il marchez ca fiind vizitat

 

p=p->next;

 

}

 

prim++; //avansez la urmatorul nod din coada}}

 

void afisare(int 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;

 

nod  *p,*q;

 

f.open(“muchii.txt”,ios::in);

 

clrscr();

 

f>>n>>m;

 

while(f>>i>>j)

 

{p=new nod;

 

p->nd=j;

 

p->next=L[i];

 

L[i]=p;

 

q=new nod;

 

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

 

int ndr;

 

cout<<endl<<“nodul de inceput “;

 

cin>>ndr;

 

viz[ndr]=1;

 

prim=ultim=1;

 

C[prim]=ndr;

 

cout<<endl<<“parcurgere in latime “<<endl;

 

bfi_lis();

 

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

 

cout<<C[i]<<” “;

 

getch();

 

}

 

Parcurgerea in adancime (DF-Depth First)

 

            Parcurgerea unui graf in adancime se face prin utilizarea stivei (alocate implicit prin subprograme recursive).

 

Pentru fiecare nod se parcurge primul dintre vecinii lui neparcursi inca

 

Dupa vizitarea nodului initial x1, se exploreaza primul nod adiacent lui fie acesta x2 , se trece apoi la primul nod adiacent cu x2 si care nu a fost parcurs inca , s.a.m.d.

 

Fiecare nod se parcurge cel mult odata (daca graful nu este conex nu se vor putea parcurge toate nodurile)

 

De exemplul pentru garful din figura de mai jos, se va proceda in felul urmator: