CUPRINS

Folosind alocarea dinamica pentru:

1. Parcurgerea în adâncime a grafurilor2. Parcurgerea în lăţime a grafurilor3. Conexitatea în grafuri neorientate4. Determinarea unui ciclu eulerian5. Puncte de articulaţie6. Componente biconexe7. Sortarea topologică a unui graf orientat aciclic8. Determinarea componetelor tare-conexe9. Folosirea metodelor de parcurgere în problema

labirintului10. Parcurgerea BF în labirint

1

Parcurgerea în adâncime a grafurilor

Printre operaţiile fundamentale efectuate asupra structurilor de date se numără şi traversarea acestora. Această operaţie constă într-o căutare efectuată asupra tuturor elementelor ei. Cu alte cuvinte traversarea poate fi privită şi ca un caz special de căutare, deoarece constă în regăsirea tuturor elementelor structurii.

Strategia parcurgerii în adâncime a unui graf presupune traversarea unei muchii care pleacă din nodul curent către un nod nedescoperit. Când toate muchiile nodului curent au fost explorate, se revine în nodul care a condus la explorarea nodului curent. Procesul se repetă până în momentul în care toate nodurile au fost explorate.

Această strategie a parcurgerii DF (depth first) funcţionează respectând mecanismul LIFO (last in first out). Nodul care este eliminat din stivă nu mai are nici o muchie (arc) disponibilă pentru traversare.În procesul de parcurgere muchiile grafului se pot împărţi în:

- muchii de avans (muchii de arbore), folosite pentru explorarea nodurilor; ele formează un graf parţial format din unul (graf conex) sau mai mulţi arbori ai parcurgerii DF

- muchii de întoarcere, care unesc un nod cu un strămoş al său în arborele DFExemplu: Fie graful următor:

Parcurgerea DF furnizează nodurile în ordinea: 1 2 3 4 5Arborele parţial DF este:

Muchii de întoarcere: (1,4) şi (1,5)În implementarea parcurgerii DF se vor reţine mai multe informaţii referitoare la nodurile grafului şi anume:

2

- nodul predecesor (părinte) în parcurgere: TATA[nod]- momentul descoperirii, care coincide cu momentul de introducere a nodului în stivă: TI[nod]- momentul de finish în explorare, care coincide cu momentul extragerii din stivă: TF[nod]- muchiile de avansare: matricea a cu k linii şi 2 coloane- muchiile de întoarcere: matricea b cu t linii şi 2 coloane

Pentru graful dat ca exemplu mai sus cei trei vectori au valorile:

Este posibil să determinăm şi muchiile arborelui BF (de avansare), precum şi muchiile de întoarcere. Considerând graful G(V,E), unde V este mulţimea celor n noduri şi E este mulţimea celor m muchii, şi graful reprezentat prin listele de adiacenţă alocate dinamic, complexitatea algoritmului este O(n+m).

Programul următor implementează algoritmul DF descris mai sus. Vectorul VIZ indică la fiecare pas ce vârf a fost deja vizitat (explorat). Iniţial, toate vârfurile sunt nevizitate şi acest vector este iniţializat cu 0. În vectorul TI se memorează pentru fiecare nod timpul la care începe explorarea, iar în vectorul TF când se încheie explorarea unui nod. În vectorul TATA se memorează pentru fiecare nod predecesorul (tatăl) în parcurgerea DF. Muchile de avansare se memorează pe liniile matricii a, numărul acestor muchii fiind k. Când un nod j este parcurs plecând din nodul i, muchia [i,j] este de avansare. Când un vecin j al lui i este deja vizitat, muchia [i,j] este de întoarcere. Afişarea muchiilor de avansare, respectiv de întoarcere se realizează cu ajutorul a două funcţii recursive care folosesc matricea de adiacenţă construită simultan cu construirea listele de adiacenţă. După afişarea unei muchii, aceasta se elimină din graf.

#include<iostream.h> #include<ifstream.h>#define N 50typedef struct nod{

int inf;nod *leg;

}AD;AD *L[N]; //listele vecinilorint VIZ[N],TI[N],TF[N],TATA[N],n,timp,k,t;int a[N][N]; //matricea de adiacentavoid citire(){

int i,j; AD *x;Ifstream f(“graf.in”);f>>n; for(i=1;i<=n;i++) //aloca adrese pentru listele de vecini{

L[i]=new AD; L[i]->leg=0;

3

TI=( 1,2,3,4,6 )TF=( 10,9,8,5,7 )TATA=( 0,1,2,3,3 )Muchii avansare: [1,2],[2,3],[3,4],[3,5]Muchii întoarcere: [1,4],[1,5]

}

while(!feof(f)){

f>>i>>j; a[i][j]=a[j][i]=1;x=new AD; x->inf=j; x->leg=L[i]->leg; L[i]->leg=x; //adaug j in lista vecinilor lui ix=new AD; x->inf=i; x->leg=L[j]->leg; L[j]->leg=x; //adaug i in lista vecinilor lui j

}f.close();

}void parcurge_df(int nod){

AD *x=L[nod]->leg;VIZ[nod]=1; timp++; TI[nod]=timp; //timpul de inceperecout<<"%d ",nod);while(x){

if(!VIZ[x->inf]){

TATA[x->inf]=nod;parcurge_df(x->inf);

}x=x->leg;

}timp++; TF[nod]=timp; //timp de terminare

}void muchii_intoarcere(int nod){

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

if(a[nod][i])if(TATA[nod]!=i && nod!=TATA[i]){

cout<<“[“<<nod<<“,”<<i<<“] “;a[nod][i]=a[i][nod]=0;muchii_intoarcere(i);

}}void muchii_avans(int nod){

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

if(a[nod][i]){

cout<<“[“<<nod<<“,”<<i<<“] “;a[nod][i]=a[i][nod]=0;muchii_avans(i);

}}void DF(){

int nod;for(nod=1;nod<=n;nod++) VIZ[nod]=0;timp=0;

4

for(nod=1;nod<=n;nod++)if(!VIZ[nod]){

parcurge_df(nod); cout<<“\n”;cout<<"Muchii de intoarcere: "; muchii_intoarcere(nod);cout<<“\n”;cout<<"Muchii de avans: "; muchii_avans(nod);cout<<“\n”;

}}void main(){

int i;citire();cout<<"Parcurgerea DF: \n"); DF(); cout<<“\n”;cout<<"\nTI=("); for(i=1;i<=n;i++) cout<<TI[i]<<” ”; cout<<")";cout<<"\nTF=("); for(i=1;i<=n;i++) cout<<TF[i]<<” ”; cout<<")";cout<<"\nTATA_DF=("; for(i=1;i<=n;i++) cout<<"%d ",TATA[i];

cout<<")\n";}

Parcurgerea în lăţime a grafurilor

Strategia parcurgerii în lăţime (BF- breadth first) funcţionează respectând mecanismul de tip FIFO (first in first out). Ea se bazează pe traversarea tuturor muchiilor disponibile din nodul curent către noduri nedescoperite, care vor fi astfel vizitate. După acest proces, nodul explorat este scos din coadă, prelucrându-se succesiv toate nodurile ajunse în vârful cozii.

Acest mecanism permite identificarea drumurilor de lungime minimă (ca număr de muchii) de la nodul de start către toate vârfurile accesibile lui din graf. Arborele BF, ce cuprinde muchii traversate în parcurgerea în lăţime, are proprietatea de a fi format doar din drumuri de lungime minimă ce pornesc din nodul considerat ca rădăcină.

În parcurgerea BF, pentru fiecare nod se reţin mai multe informaţii şi anume:- nodul predecesor (tată) în parcurgere: TATA[nod]- lungimea drumului minim către nodul de start: DMIN[nod]- ordinea de parcurgere a nodurilor în BF: vectorul C- muchiile arborelui BF: matricea a cu k linii şi 2 coloane

Pentru graful următor:

5

Arborele BF este:

Complexitatea algoritmului este O(n+m).Programul următor realizează implementarea algoritmului BF pentru un graf reprezentat prin liste de adiacenţă alocate dinamic.#include<iostream.h> #include<ifstream.h>#define N 50

typedef struct nod{int inf;nod *leg;

}AD;AD *L[N]; //listele vecinilorint VIZ[N],C[N],DMIN[N],TATA[N]; // C-vectorul coadaint n,k,prim,ultim;int a[2*N][3]; //a retine muchiile arborelui BFvoid citire(){

int i,j; AD *x;Ifstream f(“graf.in”);f>>n; for(i=1;i<=n;i++) //aloca adrese pentru listele de vecini{

L[i]=new AD; L[i]->leg=0;}

while(!feof(f)){

f>>i>>j; x=new AD; x->inf=j; x->leg=L[i]->leg; L[i]->leg=x; //adaug j in lista vecinilor lui ix=new AD; x->inf=i; x->leg=L[j]->leg; L[j]->leg=x; //adaug i in lista vecinilor lui j

}f.close();

}void BF(int nod)

6

COADA=(1,2,4,5,3)DMIN=(0,1,2,1,1)TATA=(0,1,2,1,1)Muchii arbore BF:[1,2],[1,4],[1,5],[2,3]

{AD *x;VIZ[nod]=1; TATA[nod]=0; DMIN[nod]=0;prim=ultim=1; C[prim]=nod;while(prim<=ultim){

nod=C[prim]; //extrag nodul din varful coziix=L[nod]->leg; //lista vecinilor lui nodwhile(x){

if(!VIZ[x->inf]){

TATA[x->inf]=nod; VIZ[x->inf]=1;DMIN[x->inf]=DMIN[nod]+1;C[++ultim]=x->inf; //adaug x->inf in coadak++; a[k][1]=nod; a[k][2]=x->inf; //memorez muchia de arbore [nod,x->inf]

}x=x->leg;

}prim++; //avansez la urmatorul nod din coada

} }void afisare_coada() //afiseaza nodurile dintr-un arbore BF{

int i;for(i=1;i<=ultim;i++) cout<<C[i]<<” ”;cout<<“\n”;

}void drum(int i,int nod) //afiseaza nodurile dintr-un lant minim{

if(i!=nod) drum(TATA[i],nod);cout<<i<<“ “;

}void parcurgere_bf(){

int nod,i;for(nod=1;nod<=n;nod++) VIZ[nod]=0;for(nod=1;nod<=n;nod++)

if(!VIZ[nod]){

k=0; BF(nod); afisare_coada();cout<<"Muchiile arborelui BF: ";for(i=1;i<=k;i++)

cout<<"[ a[“<<i<<”][1],a[“<<i<<”][2]] ";cout<<“\n”;for(i=1;i<=ultim;i++)

if(C[i]!=nod){cout<<"de la <<nod<<” la “<<C[i]<<” lantul este: ";

drum(TATA[C[i]],nod); cout<< C[i],<<" lungime \n"<< DMIN[C[i]]<<” ”;

}

}

7

}void main(){

int i;citire();cout<<"Parcurgere BF: \n"; parcurgere_bf();cout<<"TATA_DF=("; for(i=1;i<=n;i++) cout<<TATA[i]<< " ",; cout<<")\

n";}

Conexitatea în grafuri neorientate

Un graf neorientat este conex dacă oricare ar fi două vârfuri distincte ale sale x şi y, există un lanţ între x şi y (un lanţ care le leagă).

Se numeşte componentă conexă a unui graf neorientat un subgraf conex al său, maximal în raport cu proprietatea de conexitate.

În figura de mai jos graful din stânga este conex, în timp ce graful din dreapta este neconex şi este format din trei componente conexe notate C1, C2, C3:

Pentru verificarea conexităţii cea mai simplă metodă o reprezintă parcurgerea grafului (în adîncime sau lăţime). Prin parcurgere se vizitează toate vârfurile legate prin lanţ de vârful de plecare. Dacă realizăm parcurgerea din vârful 1 şi am reuşit să vizităm toate vârfurile graful este conex. Dacă după această parcurgere au rămas vârfuri nevizitate graful nu este conex.

8

Programul următor verifică dacă un graf dat prin listele de adiacenţă este conex folosind metoda de parcurgere BF:

#include<iostream.h> #include<ifstream.h>#define N 50typedef struct nod{

int inf;nod *leg;

}AD;AD *L[N]; //listele vecinilorint VIZ[N],C[N]; // C-vectorul coadaint n,prim,ultim;void citire(){

int i,j; AD *x;Ifstream f(“graf.in”);f>>n; for(i=1;i<=n;i++) //aloca adrese pentru listele de vecini{

L[i]=new AD; L[i]->leg=0;}

while(!feof(f)){

f>>i>>j; x=new AD; x->inf=j; x->leg=L[i]->leg; L[i]->leg=x; //adaug j in lista vecinilor lui ix=new AD; x->inf=i; x->leg=L[j]->leg; L[j]->leg=x; //adaug i in lista vecinilor lui j

}f.close();

}void BF(int nod){

AD *x;VIZ[nod]=1; prim=ultim=1; C[prim]=nod;while(prim<=ultim){

nod=C[prim]; //extrag nodul din varful coziix=L[nod]->leg; //lista vecinilor lui nodwhile(x){

if(!VIZ[x->inf]){

VIZ[x->inf]=1;C[++ultim]=x->inf; //adaug x->inf in coada

}x=x->leg;

}prim++; //avansez la urmatorul nod din coada

} }void main(){

int i,conex=1;

9

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

if(!VIZ[i]) { conex=0; break; }if(conex) cout<<"Graful este conex\n";else cout<<"\nGraful nu este conex\n";

}

În multe aplicaţii nu este suficient să ştim doar dacă graful este conex, ci ne interesează vârfurile care fac parte din fiecare componentă conexă. Pentru a determina efectiv toate componentele conexe ale unui graf este suficient să reapelăm funcţia de parcurgere pentru primul nod rămas nevizitat de la parcurgerea anterioară. Fiecare astfel de nod va reprezenta rădăcina unui arbore de parcurgere. Programul următor realizează determinarea componentelor conexe dintr-un graf neorientat reprezentat prin liste de adiacenţă, folosind pentru parcurgere metoda DF:

#include<iostream.h> #include<ifstream.h>#define N 50typedef struct nod{

int inf;nod *leg;

}AD;AD *L[N]; int VIZ[N],n,nc;void citire(){

int i,j; AD *x;ifstream f(“graf.in”);f>>n; for(i=1;i<=n;i++) {

L[i]=new AD; L[i]->leg=0;}

while(!feof(f)){

f>>i>>j; x=new AD; x->inf=j; x->leg=L[i]->leg; L[i]->leg=x; x=new AD; x->inf=i; x->leg=L[j]->leg; L[j]->leg=x;

}f.close();

}void DF(int nod){

AD *x=L[nod]->leg;VIZ[nod]=1; cout<<"%d ",nod);while(x){

if(!VIZ[x->inf]) DF(x->inf);x=x->leg;

}}void main(){

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

10

if(!VIZ[i]){

cout<<"Componenta conexa “<<++nc<<”: ";DF(i); cout<<“\n”;

}}

Determinarea unui ciclu eulerian

Un ciclu al unui graf G(V,E) care conţine toate muchiile lui G (fiecare o singură dată) se numeşte ciclu eulerian. Un graf care conţine un astfel de ciclu se numeşte graf eulerian.

Existenţa unui ciclu eulerian într-un graf este rezolvată de teorema următoare:Un graf G fără vârfuri izolate este eulerian dacă şi numai dacă este conex şi gradele tuturor vârfurilor sale sunt pare.

În continuare ne punem problema determinării unui ciclu eulerian într-un graf eulerian. Această problemă este rezolvată printr-un algoritm liniar care are la bază tot parcurgerea DF a grafului:Pasul 1: se parcurge graful în adâncime pentru a identifica arborele DF (codificat în vectorul tată T)Pasul 2: în vederea obţinerii ciclului eulerian se reparcurg toate muchiile grafului urmând strategia DF dar respectând o anumită prioritate la traversarea lor:

- se înaintează mai întâi pe muchiile grafului care nu aparţin arborelui DF iniţial determinat- ori de câte ori acest lucru nu este posibil, se continuă cu parcurgerea muchiei de avans

accesibilă din nodul curent. Aceasta va conduce în final la „închiderea ciclului” şi revenirea în nodul de plecare

- la fiecare traversare a unei muchii, aceasta este eliminată din graf

Pentru graful următor:

Etapele parcurgerii sunt:

11

Pasul 1: vectorul T=(0,1,2,3,3), muchii de întoarcere (1,3) (1,4) (1,5)Pasul 2: se obţine ciclul eulerian 1 3 2 1 4 3 5 1

Programul următor ilustrează determinarea unui ciclu eulerian într-un graf eulerian reprezentat prin matricea de adiacenţă:

#include<iostream.h> #include<ifstream.h>#define N 50int a[N][N]; //matricea de adiacentaint VIZ[N],TATA[N],n;void citire(){

int i,j; Ifstream f(“graf.in”);f>>n; {

f>>i>>j; a[i][j]=a[j][i]=1;

}f.close();

}

void DF(int nod){

int i;VIZ[nod]=1; for(i=1;i<=n;i++)

if(!VIZ[i]){

TATA[i]=nod; DF(i);}

}void euler(int nod){

int i;cout<< nod <<" ";for(i=1;i<=n;i++) //parcurg muchia de intoarcere

if(a[nod][i])if(TATA[nod]!=i && nod!=TATA[i]){

a[nod][i]=a[i][nod]=0; //elimin muchia din grafeuler(i);

}for(i=1;i<=n;i++) //parcurg muchia de avans

12

Nod curent 1 - parcurg muchia de întoarcere (1,3)Nod curent 3 – parcurg muchia de avans (3,2)Nod curent 2 – parcurg muchia de avans (2,1)Nod curent 1 – parcurg muchia de întoarcere (1,4)Nod curent 4 – parcurg muchia de avans (4,3)Nod curent 3 – parcurg muchia de avans (3,5)Nod curent 5 – parcurg muchia de întoarcere (5,1)Nod curent 1 – muchii epuizate

if(a[nod][i]){

a[nod][i]=a[i][nod]=0; //elimin muchia din grafeuler(i);

}}void main(){

citire(); DF(1);cout<<"CE: "; euler(1);

}

Puncte de articulaţie

Un vârf din graful G(V,E) neorientat conex este punct de articulaţie (critic) dacă şi numai dacă prin eliminarea lui, împreună cu muchiile adiacente acestuia, se pierde proprietatea de conexitate.

Determinarea mulţimii punctelor de articulaţie poate fi realizată printr-un algoritm liniar de complexitate O(n+m). Acest algoritm are la bază o parcurgere DF în care se reţin mai multe informaţii despre fiecare nod, informaţii care vor conduce în final la identificarea punctelor de articulaţie. Pentru fiecare vârf xV se vor identifica:

- numărul nivelului atins în parcurgerea DF, memotat în vectorul VIZ pe poziţia VIZ[x]- numărul minim al nivelului care poate fi atins din x folosind descendenţii săi şi cel mult o

muchie de întoarcere. Intuitiv este vorba de „cel mai de sus” nivel care poate fi atins din x prin intermediul muchiilor de întoarcere accesibile din el sau din descendenţii săi. Acest număr va fi reţinut în vectorul H pe poziţia H[x]

- vârful părinte în arborele DF, reţinut în vectorul TATA pe poziţia TATA[x]La finalul algoritmului, dacă dintr-un nod x din graf nu se poate ajunge pe un nivel strict mai mic decât al tatălui său din arborele DF (VIZ[TATA[x]]≤H[x]), atunci TATA[x] este punct de articulaţie. Eliminarea acestui nod, împreună cu muchiile adiacente, ar duce la izolarea nodului x.

Considerăm graful din figura de mai jos. El conţine două puncte de articulaţie: nodul 3 şi nodul 5.

Arborele DF al acestuia cu rădăcina în nodul 1 are patru niveluri. Vectorii descrişi anterior au următoarele configuraţii:

TATA=(0,5,1,6,3,3)VIZ=(1,4,2,4,3,3)H=(1,4,1,2,1,2)

13

Avem H[3]=1 deoarece nivelurile minime atinse de descendenţii săi sunt:- nivelul 2 pentru nodul 4 (H[4]=2)- nivelul 1 pentru nodul 5 (H[5]=1)- nivelul 2 pentru nodul 6 (H[6]=2)- nivelul 4 pentru nodul 2 (H[2]=4)

Nivelul minim atins din nodul 3 prin intermediul descendenţilor săi şi al unei muchii de întoarcere este nivelul 1.

Cum pentru nodul 3 exista descendentul direct 6 care nu poate atinge un nivel mai mic decât cel pe care este situat el, rezultă că 3 este punct de articulaţie ( VIZ[TATA[6]]=VIZ[3]≤H[6] ). Analog pentru nodul 5 ( VIZ[TATA[2]]=VIZ[5]≤H[2] ).

De reţinut că nodul rădăcină al arborelui DF este punct de articulaţie dacă are mai mult de un singur descendent direct.

Programul următor implementează algoritmul descris mai sus pentru grafuri reprezentate prin liste de adiacenţă alocate dinamic. Funcţia DF_PA construieşte prin parcurgere DF vectorii VIZ, H şi TATA. Această funcţie este apelată din funcţia Determina care primeşte şi analizează valorile acestor vectori, detectând punctele de articulaţie.

#include<iostream.h> #include<ifstream.h>#define N 50typedef struct nod{

int inf;nod *leg;

}AD;AD *L[N]; //listele vecinilorint VIZ[N],TATA[N],H[N],P[N],n,m;void citire(){

int i,j; AD *x;Ifstream f(“graf.in”);f>>n; for(i=1;i<=n;i++) {

L[i]=new AD; L[i]->leg=0;}

while(!feof(f)){

f>>i>>j; x=new AD; x->inf=j; x->leg=L[i]->leg; L[i]->leg=x; x=new AD; x->inf=i; x->leg=L[j]->leg; L[j]->leg=x;

}f.close();

}void DF_PA(int nod,int niv){

AD *x;if(niv==2) m++; //numar descendentii radaciniiVIZ[nod]=niv; H[nod]=niv;x=L[nod]->leg;while(x){

if(!VIZ[x->inf]){

TATA[x->inf]=nod;

14

DF_PA(x->inf,niv+1);if(H[x->inf]<H[nod]) H[nod]=H[x->inf];

}else

if(VIZ[x->inf]<H[nod] && x->inf!=TATA[nod])H[nod]=VIZ[x->inf];

x=x->leg;}

}void Determina(){

int i;for(i=1;i<=n;i++) VIZ[i]=P[i]=0;m=0; TATA[1]=0;DF_PA(1,1);if(m!=1) P[1]=1; //radacina are mai multi descendenti, este punct de articulatiefor(i=2;i<=n;i++)

if(TATA[i]>1 && H[i]>=VIZ[TATA[i]]) P[TATA[i]]=1;cout<<"Puncte de articulatie: ";for(i=1;i<=n;i++)

if(P[i]) cout<<i<<“ “;cout<<“\n”;

}void main(){

citire(); Determina();}

Componente biconexe

Prin definiţie, un graf G(V,E) este biconex dacă nu conţine puncte de articulaţie. Prin componentă biconexă se înţelege un subgraf maximal în raport cu proprietatea de biconexitate.

Algoritmul de determinare a componentelor biconexe are la bază parcurgerea DF a grafului, de aici şi complexitatea liniară a acestuia O(n+m). În fapt, algoritmul constă în două etape:

- parcurgerea DF pentru determinarea numărului minim al nivelului care poate fi atins din fiecare nod folosind descendenţii acestuia şi cel mult o muchie de întoarcere. Aceste numere vor fi reţinute în vectorul H (conform algoritmului descris la puncte de articulaţie)

- reparcurgerea grafului în DF pentru afişarea nodurilor din fiecare componentă biconexă. Această operaţie se va realiza memorându-se explicit stiva obţinută în parcurgere. Când un nod neafişat anterior sau punct de articulaţie iese din stivă se va afişa o nouă componentă conexă. Ea va fi formată din secvenţa de noduri succesive din stivă până la următorul punct de articulaţie, adică cel situat pe nivelul minim ce poate fi atins prin intermediul muchiilor de întoarcere

Considerând ca exemplu graful următor se vor obţine trei componente biconexe:

15

Etapele algoritmului:

b)Pasul 1:Nodul 4 părăseşte stiva DF: st=(1,3,6,4)Se afişează componenta biconexă formată din succesiunea de noduri până la primul punct de articulaţie: 4 6 3Pasul 2:Nodul 2 părăseşte siva DF: st=(1,3,5,2)Se afişează componenta biconexă formată din succesiunea de noduri până la primul punct de articulaţie: 2 5Pasul 3:Nodul 5 părăseşte stiva DF: st=(1,3,5)Se afişează componenta biconexă formată din succesiunea de noduri până la primul punct de articulaţie: 5 3 1Pasul 4:Stiva este vidă, algoritmul se încheie.

Implementarea algoritmului a fost făcută prin modificarea funcţiei Determina() realizată în cadrul programului pentru puncte de articulaţie. Această funcţie va conţine în plus şi apelul DF_BIC() care realizează afişarea componentelor biconexe.

16

a) După prima parcurgere DF se obţin vectorii:

TATA=(0,5,1,6,3,3)VIZ=(1,4,2,4,3,3)H=(1,4,1,2,1,2)

#include<iostream.h> #include<ifstream.h>#define N 50typedef struct nod{

int inf;nod *leg;

}AD;AD *L[N]; //listele vecinilorint VIZ[N],TATA[N],H[N],ST[N],VER[N],n,m;void citire(){

int i,j; AD *x;Ifstream f(“graf.in”);f>>n; for(i=1;i<=n;i++) {

L[i]=new AD; L[i]->leg=0;}

while(!feof(f)){

f>>i>>j; x=new AD; x->inf=j; x->leg=L[i]->leg; L[i]->leg=x; x=new AD; x->inf=i; x->leg=L[j]->leg; L[j]->leg=x;

}f.close();

}void DF_PA(int nod,int niv){

AD *x;if(niv==2) m++; VIZ[nod]=niv; H[nod]=niv;x=L[nod]->leg;while(x){

if(!VIZ[x->inf]){

TATA[x->inf]=nod;DF_PA(x->inf,niv+1);if(H[x->inf]<H[nod]) H[nod]=H[x->inf];

}else

if(VIZ[x->inf]<H[nod] && x->inf!=TATA[nod])H[nod]=VIZ[x->inf];

x=x->leg;}

}void DF_BIC(int nod,int niv){

int i,j;AD *x;ST[niv]=nod; VIZ[nod]=1;x=L[nod]->leg;while(x){

if(!VIZ[x->inf]) DF_BIC(x->inf,niv+1);

17

x=x->leg;}if(niv>1 && !VER[nod]){

i=niv; j=niv-1;while(i>j){

if(H[ST[i]]<j) j=H[ST[i]];VER[ST[i]]=1; i--;

}cout<<"Componenta biconexa: "; for(i=j;i<=niv;i++) cout<<ST[i]<<” “; cout<<“\n”;

}}void Determina(){

int i;for(i=1;i<=n;i++) VIZ[i]=0;m=0; TATA[1]=0;DF_PA(1,1);for(i=1;i<=n;i++) VIZ[i]=VER[i]=0;DF_BIC(1,1);

}void main(){

citire(); Determina();}

Sortarea topologică

O sortare topologică a unui graf orientat aciclic G(V,E) este o ordonare liniară a tuturor nodurilor astfel încât, dacă G conţine un arc (u,v), atunci u apare înaintea lui v în ordonare.

Dacă un graf nu este aciclic, atunci nu este posibilă nici o ordonare liniară. O sortare topologică a unui graf orientat poate fi văzută ca o ordonare a nodurilor sale de-a lungul unei linii orizontale, astfel încât toate arcele sale sunt orientate de la stânga la dreapta. Sortarea topologică este deci diferită de tipul normal de ordonare. Grafurile aciclice sunt folosite în multe aplicaţii pentru a indica precedenţa între evenimente. Un arc (u,v) într-un astfel de graf, indică faptul că evenimentul u trebuie realizat înaintea evenimentului v.Dacă considerăm graful orientat aciclic de mai jos:

18

După rearanjarea nodurilor în ordinea descrescătoare a timpilor de finish obţinem graful:

Pentru sortarea topologică a unui graf orientat aciclic se foloseşte următoril algoritm:- apelează parcurgerea în adâncime DF pentru a calcula timpii de terminare TF[v] pentru

fiecare nod v- pe măsură ce fiecare nod este terminat, inserează-l la începutul unei liste- afişează lista obţinută

În programul următor graful este reprezentat prin listele de adiacenţă. În momentul în care un nod este terminat, fără a se mai calcula timpii de finish, este introdus în lista m implementată cu ajutorul unui vector care se completează da la sfârşit către început.

#include<iostream.h> #include<ifstream.h>#define N 50#define INF 32000typedef struct nod{

int inf;nod *leg;

}AD;AD *L[N]; //listele vecinilorint viz[N],m[N],n,k;void citire(){

int i,j; AD *x;ifstream f(“graf.in”);f>>n; for(i=1;i<=n;i++) //aloca adrese pentru listele de vecini{

L[i]=new AD; L[i]->leg=0;

19

}while(!feof(f)){

f>>i>>j; x=new AD; x->inf=j; x->leg=L[i]->leg; L[i]->leg=x; //adaug j in lista vecinilor lui i

}f.close();

}void Init(){

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

viz[i]=0; m[i]=0;}k=n;

}void DF_TOP(int i){

AD *x=L[i]->leg; //lista vecinilor lui iviz[i]=1; while(x){

if(!viz[x->inf]) DF_TOP(x->inf);x=x->leg;

}//i a fost complet explorat, il adaug la inceputul listei mm[k]=i; k--; //m contine nodurile in ordine topologica

}void Parcurge(){

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

if(!viz[i]) DF_TOP(i);}void afisare(){

int i;cout<<"Ordinea topologica: ";for(i=1;i<=n;i++) cout<<m[i]<< " ";cout<<“\n”;

}void main(){

citire(); Parcurge(); afisare();}

20

Tare conexitate

În cazul grafurilor orientate o componentă tare conexă reprezintă un subgraf maximal în care oricare două noduri sunt accesibile unul din celălalt.

Intuitiv, o componentă tare conexă reprezintă un circuit nu neapărat elementar. În cadrul unui astfel de circuit, inversarea sensului de deplasare nu implică blocarea accesului către vreunul din nodurile sale.

Algoritmul propus identifică componenta tare conexă a unui nod ca fiind intersecţia dintre mulţimea nodurilor accesibile din el în graful iniţial şi mulţimea nodurilor accesibile din el în graful transpus (obţinut prin inversarea sensurilor arcelor). Acest algoritm se bazează pe parcurgerea DF a celor două grafuri, de aici şi complexitatea liniară a acestuia. Operaţiile efectuate sunt:

1. Parcurgerea DF a grafului iniţial pentru memorarea explicită a stivei în ordinea inversă a timpilor de finish ai nodurilor.

2. Parcurgerea DF a grafului transpus pornind în ordine cu nodurile reţinute în stiva obţinută la pasul 1. Nodurile fiecărui arbore DF obţinut la acest pas reprezintă o componentă tare conexa.

Pentru graful:

Pasul 1: Stiva DF conţine nodurile în ordinea inversă a timpilor de finish: ST1=(1,2,3,5,4)Pasul 2:Parcurgerea DF pe graful transpus din nodul ST1[1] accesează nodurile 1,4,3,2 – prima componentă tare conexăParcurgerea DF din nodul ST1[4] accesează doar nodul 5 – a doua componetă tare conexă

Programul următor determină componentele tare conexe într-un graf orientat reprezentat prin matricea de adiacenţă.

#include<iostream.h> #include<ifstream.h>#define N 50int a[N][N],ST1[N],ST2[N],VIZ[N],n,x;void citire(){

int i,j; Ifstream f(“graf.in”);f>>n; while(!feof(f)){

21

Graful iniţial Graful transpus

f>>i>>j; a[i][j]=1;

}f.close();

}void DF_TC(int nod,int nr,int ST[]){

int j,arc;VIZ[nod]=1;for(j=1;j<=n;j++){

if(nr==2) arc=a[j][nod]; //graf transpuselse arc=a[nod][j]; //graf initialif(arc && !VIZ[j]) //j este accesibil si nevizitat

DF_TC(j,nr,ST);}x--; ST[x]=nod; //memoram nodul in stiva DF

}void tare_conex(){

int i,j;for(j=1;j<=n;j++) VIZ[j]=0;x=n+1;for(i=1;i<=n;i++)

if(!VIZ[i]) DF_TC(i,1,ST1); //parcurg graful initial cu ST1for(j=1;j<=n;j++) VIZ[j]=0;for(i=1;i<=n;i++)

if(!VIZ[ST1[i]]) //parcurg graful transpuns in ordinea data de ST1{

x=n+1;DF_TC(ST1[i],2,ST2); //memorez ordinea in ST2cout<<"Componenta tare conexa: ";for(j=n;j>=x;j--) cout<<ST2[j]<< " ",;cout<<“\n”;

}}void main(){

citire();tare_conex();

}

Folosirea metodelor de parcurgere în problema labirintului

Considerăm un labirint ca fiind o construcţie pătratică formată din camere (celule). Un labirint se poate codifica printr-o matrice A de ordin n în care intrarea aij este un număr între 0 şi 15 cu următoarea semnificaţie: dacă se consideră vecinii camerei (i,j) în ordinea nord, est, sud, vest şi se reţine 1 în cazul existenţei unei uşi spre vecinul respectiv şi 0 în caz contrar, numărul binar de patru cifre astfel format este convertit în baza 10. Se cere determinarea drumului de lungime minimă de ieşire din labirint.Observaţie: O uşă se poate deschide în ambele direcţii, deci nu orice tablou pătratic având ca elemente numere între 0 şi 15 codifică un labirint; elementele tabloului nu sunt total independente.

22

Deşi se consideră că ieşirea din labirint nu se poate rezolva în timp polinomial, vom arăta că putem găsi un drum de ieşire din labirint într-un timp O(n2) abordând problema prin teoria grafurilor. Mai mult, determinarea drumului de lungime minimă de ieşire dintr-un labirint poate fi realizată şi ea într-un timp O(n2).

Distanţa dintre două camere se presupune a fi constantă şi egală cu 1. Un labirint este de fapt un graf cu n2 vârfuri şi cu mai puţin de 4n2 muchii. Drept noduri considerăm camerele, iar drept muchii uşile dintre camere. O parcurgere DF a acestui graf se efectuează într-un timp O(n2), aplicarea acestui algoritm asigură deja găsirea unei soluţii în timp O(n2). Algoritmul de parcurgere DF este următorul:algoritm DF(i)

viziteaza nodul imarcat(i)adevaratpentru toti vecinii j ai lui i pentru care marcat(j)=fals executa

DF(j)sfarsit pentru

Iniţializăm marcajele cu valoarea 0 şi apelăm procedura pentru camera de plecare.Pe acelaşi graf putem aplica o parcurgere de tip BF în care vom determina în paralel

distanţele minime de la camera de plecare la toate celelalte camere (algoritmul lui Lee). Oprim execuţia parcurgerii BF în momentul în care ajungem într-o cameră de ieşire. Algoritmul lui Lee este prezentat în continuare:algoritm Lee(i)

CoadavidaStivavidaviziteaza nodul imarcaj(j) adevaratd0Coada(i,0,d)cat timp Coada nu este vida executa

(i,pred_i,d) CoadaStiva(i,pred_i)pentru toti vecinii j ai lui i ptr. care marcat(j)=fals executa

viziteaza nodul jmarcaj(j) adevaratCoada(j,i,d+1)

sfarsit pentrusfarsit cat timp

În acest caz iniţializăm de asemenea marcajele cu 0 şi apelăm procedura de parcurgere din camera de plecare. Ordinul de complexitate al acestei parcurgeri BF este liniar în numărul de noduri ale grafului, deci este O(n2) în cazul problemei de faţă.

Drumul de la prima cameră de ieşire găsită la camera de plecare se poate determina printr-o singură parcurgere în sens invers a vectorului Stiva. Acest vector are dimensiunea de cel mult n2. Să analizăm mai atent algoritmul:

Coada va conţine o listă de noduri vizitate Fiecare nod este vizitat şi intră în coadă o singură dată Prelucrarea unei camere, cu alte cuvinte vizitarea vecinilor nemarcaţi, se execută la

extragerea din coadă. În final în Stiva se vor afla toate nodurile prelucrate până în momentul găsirii camerei de ieşire, fiecare din ele având legătura înapoi către camera de pornire (prin concatenarea acestor legături se determină drumul cel mai scurt).

În concluzie, problema găsirii drumului optim de ieşire este rezolvată folosind algoritmul lui Lee, tot într-un timp O(n2).

În continuare vom rafina analiza complexităţii notând cu n1 numărul de noduri care pot fi efectiv parcurse (cele din componenta conexă care conţine camera de pornire) şi cu m1 numărul de muchii ale acestei componente conexe. Ambii algoritmi prezentaţi anterior au ordinul de complexitate O(n1+m1).

23

Problema reală a omului prins în labirint este de fapt o reformulare a problemei iniţiale şi anume transformarea ei într-o problemă cu informaţie incompletă. Labirintul este dat în întregime la început, dar omul prins în labirint nu dispune de întreaga sa hartă. În camera de pornire nu cunoaşte la început decât existenţa a cel mult patru uşi de legătură cu vecinii direcţi (nord, este, sud şi vest). Nu va cunoaşte existenţa unei uşi între nodurile i şi j până când nu ajunge fie în camera i, fie în camera j. De aici rezultă că la aplicarea oricărui algoritm de ieşire din labirint trebuie impusă condiţia ca această parcurgere să fie efectuată „din cameră în cameră”.

Cu alte cuvinte, în analiza complexităţii acestor algoritmi este natural să considerăm ca operaţie fundamentală trecerea dintr-o cameră în camera vecină. În caul parcurgerii DF numărul de operaţii fundamentale efectuate coincide cu numărul de vizitări. Dacă renunţăm la optimalitate, prin acest algoritm găsim o ieşire din labirint într-un timp O(n1). Vom arăta că aplicarea algoritmului lui Lee duce la un timp de ordinul O(n1

2).Prin acest algoritm putem reţine în permanenţă, pentru fiecare cameră vizitată, lanţul care o

uneşte cu camera de pornire. Acest lucru poate fi realizat eliminând stiva, şi introducând în coadă fiecare nod vizitat împreună cu întreg lanţul care îl uneşte de nodul de plecare. Deoarece următoarea cameră care trebuie prelucrată este prima de ieşire din coadă, pentru a o putea accesa este suficient să parcurgem lanţul din camera curentă (ultima prelucrată) în camera de plecare şi apoi din camera de plecare în camera care trebuie prelucrată. Distanţa maximă dintre oricare două camere este n1-1, deci acest pas de parcurgere „din cameră în cameră” este realizat în maxim 2n1 paşi. Pasul trebuie repetat pentru fiecare din cele n1 camere. În concluzie complexitatea în timp devine O(n1

2) în raport cu operaţia fundamentală considerată.

Vom descrie acum un labirint pentru care aplicarea parcurgerii BF astfel modificată duce la un timp pătratic faţă de mulţimea efectivă de noduri. Considerăm de la sud la nord lanţul de camere 1,2,...,n1, camera de pornire fiind n1, iar spre este lanţul n1+1,n1+2,...,2n1. Conform algoritmului vom trece din camera n1-i în camera n1+i pentru fiecare i. Suma deplasărilor va fi 2(1+2+..+n1), deci ordinul de complexitate va fi O(n1

2).Consumul de memorie suplimentară este foarte mare; omul prins în labirint trebuie să reţină în

permnenţă date referitoare la subgraful deja parcurs. Iată două argumente care conduc şi ele către alegerea parcurgerii DF. Concret, în plan, aceasta revine la următoarele: la fiecare intersecţie se alege drumul cel mai din stânga şi, în plus, trebuie să existe un „fir al Ariadnei” care leagă în permanenţă camera curentă de camera de plecare. Vom prezenta şi o condiţie suficientă pentru a ne putea dispensa de acest „fir al Ariadnei”, precum şi motivul pentru care este necesar în cazul general.

În continuare vom considera că grafurile care reprezintă labirintul sunt „scufundate” în plan. Astfel vom putea da o orientare muchiilor din fiecare cameră de intersecţie, deoarece planul poate fi considerat ca fiind orientat. Corectitudinea următorilor algoritmi se bazează pe astfel de raţionamente de orientare. Dacă labirintul reprezintă un graf care este şi arbore, atunci în parcurgerea sa putem face abstracţie de conţinutul stivei. De fapt, vom descrie un algoritm de parcurgere în plan a unui arbore fără memorie suplimentară. Ideea de bază este de a alege la fiecare intersecţie cel mai din stânga drum (care, la limită, este uşa pe care tocmai am intrat).algoritm arbore(i)

i0iscrie idN //directia nordrepeta

dsucc(succ(succ(succ(d)))) //prima la stangacat timp nu exista nod pe directa d executa

dsucc(d)sfarsit cat timpjun nod de pe directia dijscrie i

pana cand i=i0Observaţii:

24

Considerăm cele patru direcţii nord, est, sud, vest şi definim funcţia succ astfel încât succ(nord)=est, succ(est)=sud, succ(sud)=vest, succ(vest)=nord. Arborele va avea cel puţin două noduri.

În cazul existenţei unui posibil circuit în labirint acest algoritm poate eventual intra într-un ciclu infinit. Aşadar acesta este un algoritm euristic.

Există camere vizitate de mai multe ori. O vizitare este indicată de un apel scrie. În cazul real ordinul de complexitate este O(n1)

Aşa cum am mai spus, din punctul de vedere al omului prins în labirint, problema este cu informaţie incompletă. Deoarece labirintul în care a fost prins Tezeu, nu era neapărat de tip arbore, el a avut nevoie de „firul Ariadnei” şi a ales cu siguranţă parcurgerea DF. Ca memorie suplimentară este folosit doar un vector de marcaj de lungime n1 (elementele marcate constituie „firul Ariadnei”). Algoritmul este următorul:algoritm Tezeu(i)

viziteaza nodul imarcaj_vizit(i)adevaratscrie ipred0dN //directia nordmarcaj(i) adevaratrepeta

dsucc(succ(succ(succ(d)))) //prima la stangacat timp nu exista nod pe directia d sau exista nod marcat

pe directia d si nodul marcat de pe directia d nu este predecesorul nodului curent executa

dsucc(d)sfarsit cat timpjun nod de pe directia ddaca nu marcat_vizit(i) atunci

vizitează nodul imarcat_vizit(i) adevarat

sfarsit dacadaca j=pred atunci marcaj(i) fals

altfel marcaj(i) adevaratsfarsit dacaijscrie idaca exista p vecin al lui i si marcaj(p)

atunci predpaltfel stop

sfarsit dacapana cand fals

Să analizăm algoritmul: Pentru fiecare nod, după vizitare, determinăm predecesorul acestuia ca fiind acel unic vecin

care este şi marcat Singurul nod care nu are predecesor în acest punct va fi nodul de pornire (este totuşi şi el

marcat) După calculul predecesorului prin tehnica „prima la stânga” calculăm succesorul nodului i.

Trebuie tratate două cazuri: succesorul coincide sau nu cu predecesorul. Aceste cazuri sunt tratate corespunzător actualizării „firului Ariadnei”.

Observaţii: Ca memorie suplimentară se folosesc doar doi vectori de biţi În raport cu operaţia fundamentală algoritmul are ordinul de complexitate O(n1) producând la

ieşire un circuit cu 2(n-1) muchii, circuit ce parcurge arborele DF.

25

Circuitul tare-parcurgerii este listat prin apeluri scrie.

Problemele de parcurgere prezentate se extind natural la cazul unui graf conex. Acest graf este dat prin listele de adiacenţă, pentru fiecare nod reţinându-se şi gradul său. Aşadar regula „prima la stânga” poate fi uşor generalizată. Problema reală a labirintului conduce în mod natural la următoarea noţiune de tare-parcurgere a unui graf:

Definiţie: Fie un graf neorientat G(V,E). Vom numi o tare-parcurgere a sa un circuit care trece cel puţin o dată prin toate vârfurile grafului G, împreună cu o alegere pe acest circuit a mulţimii vârfurilor lui G.Observaţie

Noţiunea de parcurgere de până acum însemna o liniarizare (listare sau altă operaţie) a nodurilor grafului, aşadar o tare-parcurgere determină o parcurgere prin nodul său de plecare. Vom spune că tare-parcurgerea este conformă cu parcurgerea determinată de ea.Să rezumăm:

- În primii doi algoritmi vizitarea nodurilor poate fi pusă în corespondenţă cu listarea circuitului corespunzător unei tare-parcurgeri. Prin utilizarea unui vector suplimentar de marcaj care la început are toate valorile setate pe 0, şi executarea unei operaţii asupra lui la prima vizitare (de exemplu, marcarea lui ca nod ales pe circuit), se completează generarea unei tare-parcurgeri conform definiţiei date. În concluzie, parcurgerea DF poate fi imediat adaptată să furnizeze o tare-parcurgere conformă cu parcurgerea propriu-zisă. Algoritmul nu este optim în raport cu operaţia fundamentală (furnizează o tare-parcurgere de circuit de lungime minimă).

- În cele prezentate anterior am adaptat algoritmul BF (Lee) care acum poate furniza o tare-parcurgere conformă cu parcurgerea clasică, în ordinea distanţelor minime de la nodul de plecare. Complexitatea este O(n1

2) în raport cu operaţia fundamentală.- Ne punem problema dacă orice algoritm de parcurgere poate fi adaptat pentru a genera o

tare-parcurgere conformă cu respectiva parcurgere.

Algoritmul de parcurgere D (Depth)

Prezentăm în continuare descriera în pseudocod a algoritmului clasic de parcurgere D:algoritm D(i)

viziteaza nodul imarcat(i)adevaratSTIVAvidarepeta

pentru toti vecinii j ai lui i ptr. care marcat(j)=fals executaviziteaza nodul jmarcat(j)adevaratSTIVAj

sfarsit pentrudaca STIVA=vida atunci stop altfel STIVAisfarsit daca

pana cand fals

Observaţii: Stiva conţine o listă de noduri vizitate şi neprelucrate La fiecare pas al buclei repeta prelucram un nod curent i; în acest moment toate nodurile

aflate în stivă au proprietatea că sunt legate de un nod din drumul de la nodul de plecare la nodul i, drum care va fi memorat, pentru simplitate, în altă stivă auxiliară.

Ordinul de complexitate al algoritmului este O(n1+m1).

Prezentăm în continuare descrierea în pseudocod a adaptării sale pentru a genera o tare-parcurgere conformă.

26

algoritm D_tare(i)viziteaza nodul imarcat(i)adevaratSTIVAvidaST_AUXiscrie irepeta

pentru toti vecinii j ai lui i ptr. care marcat(j)=fals executaviziteaza nodul jmarcat(j)adevaratSTIVAj

sfarsit pentruST_AUXvarful stivei STIVAscrie varful stivei STIVAdaca STIVA=vida atunci stop

altfel STIVAirepeta

ST_AUXxscrie x

pana cand x este vecin cu iST_AUXx

sfarsit dacapana cand fals

ConcluziiAdaptarea algoritmului D generează la rândul său o tare-parcurgere de circuit de lungime

minimă. De fapt, tare-parcurgerea generată de ambii algoritmi este identică din punctul de vedere al circuitului parcurs.

Parcurgere BF în labirint

Enunţ: Se consideră un labirint codificat sub forma unei matrici de n*n caractere reprezentând camerele labirintului. Caracterul „o” semnifică o cameră liberă, iar caracterul „*” o cameră ocupată. Matricea este dată în fişierul lab.in, prima linie a acestuia conţinând dimensiunea n a labirintului. Dându-se o cameră de plecare (xi,yi) şi o cameră de sosire (xf,yf), evident neocupate, să se determine cel mai scurt drum de la camera de plecare până la camera de sosire ştiind că dintr-o cameră liberă ne putem deplasa într-o altă cameră vecină liberă aflată la stânga, la dreapta, deasupra sau dedesubtul camerei curente.

Citirea labirintului din fişier se face prin crearea unei matrici L astfel: 0, dacă avem cameră ocupată, adică *L[i,j]= 1, dacă avem cameră liberă, adică o

Vom ataşa acestei probleme un graf neorientat cu n*n noduri reprezentând camerele labiruntului, ele fiind numerotate în ordine 1,2,..,n*n. Dacă două camere sunt libere şi învecinate, atunci în graf cele două noduri vor fi adiacente. Vom memora graful prin liste de adiacenţă alocate dinamic.Pe baza matricii L şi a regulilor de vecinătate din enunţ vom construi listele de adiacenţă în număr de n*n astfel:

27

- cum avem n*n camere, la generarea unui vecin ne vom referi la configuraţia labirintului astfel: nodul i din graf corespunde camerei (x=(i-1)/n+1,y=(i-1)%n+1) din labirint (relaţii obţinute prin liniarizarea matricii L)

- reciproc, nodul reprezentat de (x,y) este elementul p=n*(x-1)+y din matricea L.În acest fel se verifică toate camerele libere vecine şi se completează listele de adiacenţă.

Observaţie: Complexitatea algoritmul devine O(n2) folosim o parcurgere BF a grafului reprezentat prin liste de adiacenşă şi ataşăm nodurilor un vector de marcare (algoritmul lui Lee).

Programul următor determină un drum minim între camera de plecare nod_i şi camera de sosire nod_f folosind parcurgerea BF pe un graf reprezentat prin liste de adiacenţă alocate dinamic. Tablourile utilizate de parcurgerea BF sunt alocate dinamic în heap pentru a mări spaţiul de memorie disponibil programului.

#include<iostream.h> #include<ifstream.h>#define N 50typedef struct nod{

short int inf;nod *leg;

}AD;AD *LA[N*N];short int L[N][N],n;short int *C,*T,*VIZ,*DMIN; //tablouri alocate dinamic in heapvoid citire(){

ifstream f("lab.in");char s[20]; int i,j;f>>n; fgetc(f);cout<<"\tLabirintul este:\n";for(i=1;i<=n;i++){

fgets(s,20,f); puts(s);for(j=0;j<n;j++)

if(s[j]=='*') L[i][j+1]=0;else L[i][j+1]=1;

}f.close();

}void Init() //aloca spatiu pentru tablourile C,T,VIZ,DMIN{

int i;C=new short int [n*n+1];T=new short int [n*n+1];VIZ=new short int [n*n+1];for(i=1;i<=n*n;i++) VIZ[i]=0; //initializam vectorul de vizitareDMIN=new short int [n*n+1];

}void construieste_graf(){

int i,x,y;AD *p;for(i=1;i<=n*n;i++) {

LA[i]=new AD; LA[i]->leg=0;}

28

for(i=0;i<=n+1;i++) //bordam matricea L cu 0L[0][i]=L[i][0]=L[i][n+1]=L[n+1][i]=0;

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

x=(i-1)/n+1; y=(i-1)%n+1;if(L[x][y]==1) {

if(L[x][y-1]==1) //vecin la stanga{

p=new AD; p->inf=n*(x-1)+y-1; p->leg=LA[i]->leg;LA[i]->leg=p;p=new AD; p->inf=i; p->leg=LA[n*(x-1)+y-1]->leg;LA[n*(x-1)+y-1]->leg=p;

}if(L[x][y+1]==1) //vecin la dreapta{

p=new AD; p->inf=n*(x-1)+y+1; p->leg=LA[i]->leg;LA[i]->leg=p;p=new AD; p->inf=i; p->leg=LA[n*(x-1)+y+1]->leg;LA[n*(x-1)+y+1]->leg=p;

}if(L[x-1][y]==1) //vecin deasupra{

p=new AD; p->inf=n*(x-2)+y; p->leg=LA[i]->leg; LA[i]->leg=p;p=new AD; p->inf=i; p->leg=LA[n*(x-2)+y]->leg;LA[n*(x-2)+y]->leg=p;

}if(L[x+1][y]==1) //vecin dedesubt{

p=new AD; p->inf=n*x+y; p->leg=LA[i]->leg; LA[i]->leg=p;p=new AD; p->inf=i; p->leg=LA[n*x+y]->leg; LA[n*x+y]->leg=p;

}}

}}void BF(int nod,int s){

AD *x; int prim,ultim;VIZ[nod]=1; T[nod]=0; DMIN[nod]=0;prim=ultim=1; C[prim]=nod;while(prim<=ultim){

nod=C[prim]; //extrag nodul din varful coziix=LA[nod]->leg; //lista vecinilor lui nodwhile(x){

if(!VIZ[x->inf]){

T[x->inf]=nod; VIZ[x->inf]=1;DMIN[x->inf]=DMIN[nod]+1;if(x->inf==s) return; //am ajuns in punctul de sosire, opresc parcurgereaC[++ultim]=x->inf; //adaug x->inf in coada

29

}x=x->leg;

}prim++; //avansez la urmatorul nod din coada

} }void drum(int i,int nod){

if(i!=nod) drum(T[i],nod);cout<<i<<“ “;

}void main(){

int xi,yi,xf,yf,nod_i,nod_f;citire(); construieste_graf(); Init();cout<<"punctul de plecare (x,y)="; cin>>xi>>yi;cout<<"punctul de sosire (x,y)="); cin>>xf>>yf;nod_i=n*(xi-1)+yi; nod_f=n*(xf-1)+yf;BF(nod_i,nod_f); //parcurg BF graful din nodul de plecareif(DMIN[nod_f]){

cout<<"\nlungime=”<< DMIN[nod_f]” drum prin nodurile: "<<”\n”drum(nod_f,nod_i); cout<<“\n”;

}else

cout<<"\nNu exista drum intre camera <<nod_i <<”si camera”<<nod_f;}

30

Bibliografie

1. Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Introducere in algoritmi, Editura Agora, 2000

2. Daniela Oprescu, Liana Bejan Ienulescu, Viorica Patrascu, Informatica - Manual pentru clasa a XI-a, Editura Niculescu, 2001

3. George Daniel Mateescu, Pavel Florin Moraru, Informatica - Manual pentru clasa a XI-a, Editura Niculescu 2003

4. Dana Lica, Doru Popescu Anastasiu, Radu Boriga, Dan Pracsiu, Fundamentele programarii- Culegere de probleme pentru clasele IX-XI, Editura L&S Soft 2002

5. Carpen Manuela, Suport de curs si lucrari de laborator, manuscris

31