Parcurgerea grafurilor in adancime (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 x₁, se exploreaza primul nod adiacent lui fie acesta x₂ , se trece apoi la primul nod adiacent cu x₂ 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:

se porneste din nodul 1, (se poate incepe de la oricare alt nod)

se exploreaza in vontinuare primul vecin al acestuia acestuia : nodul 2,

se obtine 1,2

dupa care din 2 se exploreaza un nod adiacent cu acesta si care nu a fost vizitat : 3.( Nodul 1 nu se mai viziteaza odata)

se obtine 1,2,3

In continuare ar trebui sa se parcurga vecinul lui 3 nevizitat : 4

se obtine 1, 2, 3, 4

Pentru nodul 4 ar trebui sa se parcurga primul sau vecin neparcurs (nodul 1 dar acesta a fost deja parcurs. Si nodul 3 a fost parcurs. Din 4 nu mai avem ce vizita si se trece la nivelul anterior din stiva, la nodul 3 :

1, 2, 3, 4 Se parcurge vecinul sau nevizitat, nodul 5 .

SE obtine : 1, 2, 3, 4 , 5.

Nodul 3 nu mai are vecini nevizitati si se trece pe nivelul anterior din stiva, nodul 2 : 1, 2, 3, 4 , 5. Nici acesta nu mai are vecini nevizitati si se trece pe nivelul anterior la nodul 1 : 1, 2, 3, 4 , 5. Cum nici acesta nu mai are vecini nevizitati se incheie algoritmul.

Nodul 6 ramane nevizitat.

Algoritmul

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

-pentru a nu parcurge un nod de doua ori se va folosi un vector boolean vizcare va retine :

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

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

-ca si la parcurgerea in latime vecinii unui nod se « cauta » pe linia acestui nod : daca a[nod][k]=1 inseamna ca nodurile nod si k sunt adiacente. Pentru ca nodul k sa fie fie parcurs trebuie ca nodul sa nu fi fost vizitat : viz[k]=0

#include<fstream.h>

#include<conio.h>

int a[20][20],n,m,viz[100],gasit;

void dfmr(int nod)

{

cout<<nod<<" ";

viz[nod]=1;

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

if(a[nod][k]==1&&viz[k]==0)

dfmr(k);

}

void main()

{int x,y,j;

fstream f;

clrscr();

f.open("graf.txt",ios::in);

if(f)

cout<<"ok!"<<endl;

else

cout<<"eroare la deschidere de fisier!";

f>>n>>m;

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

{f>>x>>y;

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

cout<<endl<<"matricea de adiacente"<<endl;

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

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

cout<<a[i][j]<<" ";

cout<<endl;}

cout<<endl<<"parcurgere in adancime incepand de la varful 1"<<endl;

dfmr(1);

getch();} 

Aplicatii :

1.Sa se parcurga graful in adancime pornind pe rand de la toate varfurile

2. Sa se determine daca pornind de la nodul x se poate ajunge la nodul y

3. Sa se determine daca se poate parcurge pornind de la un nod tot graful