APLICATIE PARCURGEREA IN ADANCIME A GRAFURILOR Problema : Se da un graf si se cere parcurgerea lui in adancime Semnificatie : examinarea in mod sistematic a nodurilor unui graf Realizare: pentru parcurgerea in adancime a unui arbore se urmaresc urmatoarele etape :
Se porneste de la un nod oarecare x.
Se alege primul vecin al lui x care nu a fost
inca vizitat.
Pentru nodul ales se reia procedeul.
Daca un nod nu are nici un vecin nevizitat se
revine la nodul vizitat anterior acestuia.
Structuri de date
necesare implementarii:
- Matrice de adiacenta (sau alte variante)
- Stiva: s (in care se memoreaza nodurile in ordinea parcurgerii).
Daca se implementeaza varianta recursiva se va folosi stiva procesorului
- Vectorul
nodurilor vizitate
Dupa sortarea listelor de adiacenta se efectueaza o parcurgere DF. In parcurgerea in adancime se utilizeaza o stiva pentru memorarea starilor posibil de atins din starea curenta. Inainte de a cauta in fratii unui nod (stare) se cauta mai intai fii acestuia. Dupa vizitarea unui nod mai intai acesta este eliminat din stiva si apoi sunt introdusi fii acestuia in vector.
DF(Nod x)
1)
marcheaza x ca fiind vizitat
2)
pentru fiecare y vecin al lui x
2.1)
daca y NU este tatal lui x
2.1.1) daca y a fost deja vizitat si nivelul lui y este mai mic decat nivelul
lui x
2.1.1.1) pune muchia (x,y) in stiva
2.1.2) daca y NU a fost deja vizitat
2.1.2.1) memoreaza ca tatal lui y este x
2.1.2.2) pune muchia (x,y) in stiva
2.1.2.3) DF(y)
2.1.2.4) daca x este nod critic relativ la y (mai exact, daca nivelul minim
accesibil al lui y este mai mare sau egal cu nivelul lui x)
2.1.2.4.1) incepe o componenta biconexa noua
2.1.2.4.2) cat timp in varful stivei nu este muchia (x,y)
2.1.2.4.2.1) scoate muchia din varful stivei si marcheaz-o ca facand parte din
componenta biconexa curenta
2.1.2.4.3) scoate din varful stivei muchia (x,y) si
marcheaz-o ca facand parte din componenta biconexa curenta
DFS (G) FOR pentru fiecare nod u I ViGs DO culoareius
ALB Gius timp FOR pentru fiecare nod u I ViGs
DO IF culoareius = ALB
THEN DFS-vizitare(u)
DFS- vizitare (u) culoare ius GRI // un nod ALB u tocmai a fost descoperit timp timp + 1 dius timp FOR pentru fiecare v I Adjius // Verifica parinte ius DO IF culoareivs = ALB THEN Gius u DFS-vizitare(v)
culoareius ALB sfarsit timp timp + 1 // Program - Codul sursa #include <iostream.h> #include <fstream.h> #define ALB 1 #define GRI 2 #define NEGRU 3 #define N 100 void initializare (int **graf, int *n, char* nume_fisier,int* culoare, int* start, int* end, int* parinte, int* aux) I fstream f (nume_fisier,ios::in);
f>
>(*n);
int i,j;
for (i=0;i<*n;i++)
for (j=0;j<*n;j++)
f>>grafiisijs;
int k;
for (k=0;k<*n;k++)
I
culoareiks=0;
startiks=0;
endiks=0;
parinteiks= auxiks=k+1;
S
f.close();
S void deinitializare (int **graf, int n, int* culoare, int* start, int* end, int* parinte, int* aux) I int i,j;
for (i=0;i<n;i++) for (j=0;j<n;j++)
grafiisijs=0;
int k;
for (k=0;k<n;k++)
I
culoareiks=0;
startiks=0;
endiks=0;
parinteiks=0;
auxiks=0;
S
S void vizitare (int n, int** graf, int u, int* culoare, int *start, int *end, int *parinte, int *timp) I culoareius=GRI;
startius=*timp;
*timp=*timp+1; int v;
for (v=0;v<n;v++)
if (grafiusivs && culoareivs==ALB)
I
parinteivs=u;
vizitare (n,graf,v,culoare,start,end,parinte,timp);
S culoareius=NEGRU;
endius=*timp;
*timp=*timp+1;
S void parcurgere_adancime (int n, int **graf, int* culoare, int* start, int* end, int* parinte, int* timp) I int k;
for (k=0;k<n;k++) I
culoareiks=ALB;
parinteiks=-1;
S
*timp=1;
for (k=0;k<n;k++)
if (culoareiks==ALB)
vizitare (n,graf,k,culoare,start,end,parinte,timp);
S void sortare_minmax (int n,int *v1,int *v2) I int i,j,temp;
for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
if (v1iis>v1ijs)
// interschimbare
I
temp=v1iis;
v1iis=v1ijs;
v1ijs=temp;
temp=v2iis;
v2iis=v2ijs;
v2ijs=temp;
S
S void afisare (int n,int *v1,int *v2,char* nume_fisier) I fstream g(nume_fisier,ios::out);
int k;
for (k=0;k<n;k++)
g<<'nodul '<
<(k+1)<<' : '<<v1iks<<'/'<<v2iks<<endl;
g.close();
S int main (int argc, char** argv) I int **graf;
int *culoare, *start, *end, *parinte;
int *aux; int n;
int timp;
int k; graf=new int* iNs;
for (k=0;k<N;k++)
grafiks=new int iNs;
culoare=new int iNs;
start=new int iNs;
end=new int iNs;
parinte=new int iNs;
aux=new intiNs; //
fisier 1
initializare (graf,&n,'input1.txt',culoare,start,end,parinte,aux); parcurgere_adancime (n
,graf,culoare,start,end,parinte,&timp);
//sortare_minmax(n,start,aux); afisare(n,start,end,'output_a_1.txt'); // fisier 2
initializare (graf,&n,'input2.txt',culoare,start,end,parinte,aux);
parcurgere_adancime (n
,graf,culoare,start,end,parinte,&timp);
//sortare_minmax(n,start,aux); afisare(n,start,end,'output_a_2.txt'); // fisier 3
initializare (graf,&n,'input3.txt',culoare,start,end,parinte,aux);
parcurgere_adancime (n
,graf,culoare,start,end,parinte,&timp);
//sortare_minmax(n,start,aux); afisare(n,start,end,'output_a_3.txt'); // fisier 4
initializare (graf,&n,'input4.txt',culoare,start,end,parinte,aux);
parcurgere_adancime (n
,graf,culoare,start,end,parinte,&timp);
//sortare_minmax(n,start,aux); afisare(n,start,end,'output_a_4.txt'); // fisier 5
initializare (graf,&n,'input5.txt',culoare,start,end,parinte,aux);
parcurgere_adancime (n
,graf,culoare,start,end,parinte,&timp);
//sortare_minmax(n,start,aux); afisare(n,start,end,'output_a_5.txt'); // fisier 6
initializare (graf,&n,'input6.txt',culoare,start,end,parinte,aux);
parcurgere_adancime (n
,graf,culoare,start,end,parinte,&timp);
//sortare_minmax(n,start,aux); afisare(n,start,end,'output_a_6.txt'); return 0;
S