Embedded Files
Parcurgerea în adâncime
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;
}
Page updated
Google Sites
Report abuse