PARCURGEREA GRAFURILOR NEORIENTATE
description
Transcript of PARCURGEREA GRAFURILOR NEORIENTATE
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