Grafuri-parcurgerea in adancime

Parcurgerea în adâncime

Implementarea acestei metode de parcurgere se face folosind o structură de date de tip stivă. Stivele sunt structuri de date în care elementele sunt inserate şi eliminate de la un capăt numit vârful stivei. Ele sunt structuri de tip LIFO ( Last In First Out - ultimul venit, primul servit). Asupra unei stive acţionează operatori specifici cum ar fi: iniţializare stivă, test de stivă vidă, adăugă un element la stivă, scoate un element din. Stivele pot fi implementate static(cu variabile de tip tablou unidimensional) sau dinamic, sau se pot utiliza tehnicile recursive. În acest caz stiva este iniţializată cu un nod oarecare al grafului, nod considerat si nod de start. La fiecare pas, pentru nodul aflat în vârful stivei, se adaugă la stivă primul vecin nevizitat al nodului respectiv. În situaţia în care nodul din vârful stivei nu mai are vecini nevizitaţi atunci el se va elimina din stivă. Algoritmul continuă în acelaşi mod pâna când au fost vizitate toate nodurile grafului.

Fie graful din figura următoare care are n = 5 noduri vom considera ca nod de start ns=1:

Vom folosi un vector v, cu un număr de elemente egal cu numărul de noduri din graf, pentru a marca nodurile vizitate. Fiecare element din vectorul v poate lua următoarele valori:

    • v[i]=0, pentru nodul i nevizitat

    • v[i]=1, pentru nodul i vizitat, unde i poate fi oricare nod din graf.

Iniţial toate nodurile grafului sunt nevizitate. După fixarea unui nod de start ns=1 acesta va fi marcat ca fiind vizitat (v[ns]=1) şi va fi aşezat în stivă. Din nodul de start plecăm către primul nod adiacent cu el şi nevizitat. pentru exemplul luat mai sus acest nod este 2:

Nodul 2 se va marca vizitat si va fi adăugat la stivă. În acest moment în vârful stivei este situat nodul 2. Aplicând în continuare algoritmul dat nodul care va fi adăugat la stivă va fi nodul de informaţie 4.

Următorul nod adăugat la stivă va fi nodul cu informaţia 3. El va fi marcat ca vizitat şi va afişat. Figura cu succesiunea nodurilor parcurse este:

În acest moment nodul din vârful stivei nu mai are noduri adiacente nevizitate si deci el trebuie eliminat din stivă. Revenim la nodul 4 şi care mai are un nod adiacent nevizitat si anume nodul de informaţie 5. Acestui nod i se aplică acelaşi algoritm: este trecut în stivă, marcat vizitat şi afişat.

În acest moment toate nodurile grafului vor fi eliminate râd pe rând din stivă, deoarece ele nu mai au noduri adiacente şi nevizitate, iar la final stiva este vidă. În acest moment algoritmul se termină, rezultatul parcurgerii în adâncime pentru graful luat ca exemplu fiind:1, 2, 4, 3, 5. Este posibil ca după un apel al funcţiei de parcurgere în adâncime începând cu un anumit vârf ns, să rămână în graf vârfuri neparcurse. În această situaţie graful nu este conex, ci este alcătuit din mai multe componente conexe, iar apelul funcţiei se va repeta pentru un alt nod ales dintre vârfurile neparcurse până la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie să asigure parcurgerea vârfului utilizat în apel.

Varianta iterativă a algoritmului de parcurgere în adâncime este:

1. citeşte n numărul de noduri din graf

2. memorează graful folosind matricea de adiacenţă

3. citeşte ns nodul de start

4. marchează ns ca fiind nod vizitat

5. afişează ns

6. afişează nodul de start ca prim nod în stivă

7. cât timp nu ai vizitat toate nodurile execută

dacă nodul din vârf mai are noduri adiacente nevizitate atunci

- îl adaugi la stivă pe primul nod adiacent cu nodul din vârf

- îl marchezi vizitat

- îl afişezi

altfel

- ştergi din stivă primul nod

sfărşit dacă

sfărşit cât timp

Varianta recursivă a algoritmului de parcurgere în adâncime

funcţia Parcurgere_în_adâncime(X)

pentru toate vârfurile k adiacente cu vârful X execută

dacă vârful k este nevizitat atunci

se parcurge în adâncime(autoapel de funcţie recursivă) vârful k: apel parcurgere_în_adâncime(k)

sfârşit dacă

sfârşit pentru

sfârşit funcţie

Programul C++ este:

#include<iostream>

#include<fstream>

using namespace std;

int a[20][20],c[20],v[20],n;

// citirea grafului din fisier text si construirea matricei de adiacenta

void citire(int a[20][20], int &n)

{ ifstream f("graf.in");

int x,y;

f>>n;

while(f>>x>>y)

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

f.close();

}

// afisarea pe ecran a matricei de adiacenta

void afisare(int a[20][20],int n)

{ cout<<"Matricea de adiacenta este : "<<endl;

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

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

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

cout<<endl;

}

}

// parcurgerea în adancime a unui graf neorientat conex

void parcurgere_adancime(int k)

{ v[k]=1;

cout<<k<<" ";

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

if(a[k][x]==1) // adiacent cu varful stivei

if(v[x]==0) //nevizitat

parcurgere_adancime(x);

}

// functia principala main()

int main()

{ citire(a,n);

afisare(a,n);

parcurgere_adancime(1);

return 0;

}

figura 3