PARCURGEREA PARCURGEREA GRAFURILOR GRAFURILOR NEORIENTATENEORIENTATE

ObiectiveObiective

Noţiuni teoretice despre parcurgeri (semnificaţie, (semnificaţie, mod de realizare, scop);mod de realizare, scop);

Metode de parcurgere;; Parcurgerea în “lăţime” (prezentarea metodei, (prezentarea metodei,

exemple);exemple); Algoritmul BF.

END

ParcurgereParcurgere (noţiuni teoretice)(noţiuni teoretice)

Semnificaţie:Semnificaţie: examinarea în mod sistematic a nodurilor unui graf; examinarea în mod sistematic a nodurilor unui graf; Realizare:Realizare: se pleacă dintr-un nod dat se pleacă dintr-un nod dat ii, astfel încât fiecare nod , astfel încât fiecare nod

accesibil din accesibil din ii pe muchii pe muchii incidenteincidente două câte două, să fie atins o singură două câte două, să fie atins o singură dată.dată.

Alte expresii similareAlte expresii similare:: vizitare, traversare. vizitare, traversare. Scop:Scop:

prelucrării informaţiilor asociate nodurilor;prelucrării informaţiilor asociate nodurilor; determinarea aranjării lineare a nodurilor în vederea trecerii determinarea aranjării lineare a nodurilor în vederea trecerii

de la unul la altulde la unul la altul Observaţii: Observaţii:

Presupunem că mulţimea vârfurilor este X=Presupunem că mulţimea vârfurilor este X={1, 2, … , n};{1, 2, … , n}; Presupunem că ordinea vârfurilor este dată de relaţia „<”, Presupunem că ordinea vârfurilor este dată de relaţia „<”,

existentă în mulţimea numerelor naturale.existentă în mulţimea numerelor naturale.

Metode de parcurgereMetode de parcurgere

Parcurgere în Parcurgere în „„lăţimelăţime”” ( (Breadth First - BF)) Parcurgerea în Parcurgerea în „adâncime„adâncime” (” (Depth First Depth First - -

DFDF))

Parcurgerea în Parcurgerea în „„lăţimelăţime”” Breadth FirstBreadth First - - BFBF

Se vizitează vârful iniţial x, apoi vecinii acestuia, apoi vecinii nevizitaţi ai acestora, şi aşa mai departe.

Exemplu:Pentru graful din figura următoare ordinea de parcurgere a nodurilor cu metoda BF, când se pleacă din vârful 1 este următoarea:

2

1

5

4

3

1,2,3,4,5.

Pentru acelaşi graf, dacă se pleacă din nodul iniţial 5, ordinea de parcurgere “în lăţime” este următoarea:

Dacă se pleacă din nodul 2, lista vârfurilor obţinută în urma parcurgerii BF este următoarea:

2

1

5

4

33.4,1,2,5,

5, 3.4,1,2,

Algoritmul BF (programul C++)

#include <iostream.h>void main (void){

int a[20][20],trecut[20],n,i,j,u,pc, m,e1,e2,x,sol[20];cout<<"numarul de noduri: ";cin>>n;cout<<"numarul de muchii: ";cin>>m;for (i=1;i<=n;i++) for (j=1;j<=n;j++) a[i][j]=0;for (i=1;i<=m;i++) { cout<<"Muchia "<<i<<":\n"; cout<<"e1="; cin>>e1; cout<<"e2="; cin>>e2; a[e1][e2]=a[e2][e1]=1; }for (i=1;i<=n;i++) trecut[i]=0;

cout<<"Nodul initial: ";cin>>x;pc=1;u=1;sol[1]=x;trecut[x]=1;while (u<n) { for (i=1;i<=n;i++) if (a[sol[pc]][i] && !trecut[i])

{ u++; sol[u]=i; trecut[i]=1; }

pc++; }cout<<"Parcurgerea BFS:";for (i=1;i<=n;i++)

cout<<sol[i]<<',';cout<<'\b';

}

Variabilele utilizate în programul C++Variabilele utilizate în programul C++ aa - - matricea de adiacenţă asociată grafului;matricea de adiacenţă asociată grafului;trecuttrecut - -vector în care se trec în ordine nodurile”parcursevector în care se trec în ordine nodurile”parcurse”;”;nn - - numărul de noduri din graf;numărul de noduri din graf;mm - - numărul de muchii din graf;numărul de muchii din graf;e1,e2e1,e2 - - extremităţile muchiilor;extremităţile muchiilor;i,ji,j - - contori;contori;xx – – nodul din care se „pleacă”;nodul din care se „pleacă”;uu - - variabilă (contor) ce ţine evidenţa numărului de noduri vizitatevariabilă (contor) ce ţine evidenţa numărului de noduri vizitate;;pcpc - - nodul ai cărui vecini îi căutăm;nodul ai cărui vecini îi căutăm;solsol - - vectorul rezultat în urma parcurgerii (conţine nodurile în ordinea vizitării vectorul rezultat în urma parcurgerii (conţine nodurile în ordinea vizitării lor). lor).

Vectorul trecut care are n componente este definit astfel:

}n..., ,2,1{j

contrar cazîn 0,

atfost vizit a j nodul dacă 1,[j]trecut

Deoarece algoritmul conţine două cicluri imbricate: unul while (care se execută de cel mult n-1 ori) şi unul for (care se execută de n ori) rezultă că ordinul de complexitate al algoritmului este O(n2).

1

2

3

4 5

6

7

89

10

11

12

Aplicaţie:

Fie graful din figura de mai jos. Se cere să se realizeze parcurgerea în “lăţime” pornind pe rând din nodurile: 1, 12, 4, 7, 8, 5 şi 10.