PARCURGEREA PARCURGEREA GRAFURILOR GRAFURILOR NEORIENTATENEORIENTATE

ObiectiveObiective

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

•Metode de parcurgere;;

•Parcurgerea în “lăţime” (prezentarea (prezentarea metodei, exemple);metodei, exemple);

•Algoritmul BF.

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

• Semnificaţie:Semnificaţie: examinarea în mod sistematic a nodurilor examinarea în mod sistematic a nodurilor unui graf;unui graf;

• Realizare:Realizare: se pleacă dintr-un nod dat se pleacă dintr-un nod dat ii, astfel încât fiecare , astfel încât fiecare nod accesibil din nod accesibil din ii pe muchii pe muchii incidenteincidente două câte două, să două câte două, să fie atins o singură dată.fie atins o singură 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 determinarea aranjării lineare a nodurilor în vederea

trecerii de la unul la altultrecerii de 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, … , {1, 2, … , n};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 - implementare

Uses crt:Var vizitat:array[1..20] of 0..1;A:array[1..20,1..20] of integer;V:array[1..20] of integer;N,m,p,u,I,k,x1,x2:integer;Procedure init;Begin

for i:= 1 to n dobeginvizitat[i]:=0;

For j:=1 to n do a[I,j]:=0;End;End;Procedure complet;BeginFor i:=1 to m doBeginReadln(x1);readln(x2);A[x1,x2]:=1; a[x2,x1]:=1;End;End;Procedure prim_vf;BeginV[1]:=I;P:=1; u:=1;Vizitat[i]:=1;End;

procedure prelucrare;BeginK:=v[p];For j:=1 to n do

if (a[k,j]=1) and(vizitat[j]=0) thenbeginu:-u+1;v[u]:=j;

Vizitat[j]:=1;End;P:=p+1;End;Procedure scrie;BeginFor j:=2 to u do write(v[j],’ ‘);End;

BeginClrscr;Readln(n0;readln(m);Init;Complet;Readln(i);Prim_vf;While p<=u do prelucrare;Scrie;End.

Variabilele utilizate în programul Variabilele utilizate în programul PASCALPASCAL

aa - - matricea de adiacenţă asociată grafului;matricea de adiacenţă asociată grafului;vv --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 grafnumărul de muchii din graf;;xx1,1,xx22 - - extremităţile muchiilor;extremităţile muchiilor;i,ji,j - - contori;contori;pp – – nodul din care se „pleacă”;nodul din care se „pleacă”;uu – – ultimul element al coziiultimul element al cozii;;kk – –vvâârful rful îîn lucrun lucru;;

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.

Informatica este un joc al Informatica este un joc al mințiiminții

prof. prof. Mirzacu Marius EmilianMirzacu Marius EmilianColegiul Național Colegiul Național ““Elena CuzaElena Cuza””

BucureBucureșștiti

Sfârșit