APLICATIE - PARCURGEREA IN ADANCIME A GRAFURILOR

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