parcurgerea grafurilor def, teoreme, cod

7/24/2019 Parcurgerea Grafurilor Def, Teoreme, Cod

1/13

Parcurgerea

Rezolvarea multor probleme de grafuri, presupune parcurgerea lor de la un anumit

nod. Pentru explorarea grafurilor, exista doua tipuri de algoritmi: de explorarea in

latime si de explorare in adancime.

Explorarea grafurilor in latime

La explorarea in latime, dupa vizitarea nodului initial, se exploreaza toate nodurile

adiacente lui, se trece apoi la primul nod adiacent si se exploreaza toate nodurile

adiacente acestuia si neparcurse inca, s.a.m.d.

Fiecare nod se parcurge cel mult odata (daca graful nu este conex nu se vor putea

parcurge toate nodurile)

De exemplul pentru garful din figura de mai os, se va proceda in felul urmator:

se porneste din nodul !, (se poate incepe de la oricare alt nod)

se exploreaza in vontinuare vecinii acestuia : nodul " si apoi #,

se obtine 1,2,4

dupa care din " se exploreaza nodul adiacent acestuia $. %odul ! nu se mai viziteazaodata

se obtine 1,2,4,3

In continuare ar trebui parcursi vecinii lui 4 (1,2,4,3 ) dar acestanu mai are vecini nevizitati si se trece la vecinii lui 3:

1,2,4,3 respectiv nodul 5 :

se obtine 1, 2, 4, 3, 5

%odul & ramane neparcurs


2/13

Algoritmul

'e va folosi o coada in care se inscriu nodurile in forma in care sunt parcurse: nodul

initial varf (de la care se porneste), apoi nodurile a,b,..., adiacente lui varf, apoi cele

adiacente lui a, cele adiacente lui b,... ,s.a.m.d.

oada este folosita astfel:

se pune primul nod in coada* se afla toate varfurile adiacente cu primul nod si se introduc dupa primul nod

se ia urmatorul nod si i se afla nodurile adiacente

procesul se repeta pana cand se aunge la sfarsitul cozii

+raful se va memora utilizand matricea de adiacenta a!-!-

pentru memorarea succesiunii nodurilor parcurse se va folosi un vector c"- care va

functiona ca o coada

pentru a nu parcurge un nod de doua ori se va folosi un vector boolean viz"- care

va retine :

viz/0- daca nodul / nu a fost vizitat inca

viz/0! daca nodul / a fost vizitat

doua variabile : prim si ultim vor retine doua pozitii din vectorul c si anume :

prim este indicele componentei pentru care se parcurg

vecinii (indexul componentelor marcate cu rosu in sirurile parcurse anterior ). Prin

urmare 1arf0cprim, este elementul pentru care se determina vecinii (nodurile

adiacente)

ultim este pozitia in vector pe care se va face o noua

inserare in vectorul c (evident, de fiecare data cand se realizeaza o noua inserare se

mareste vectorul)

vecinii nodului varf se 2 cauta 3 pe linia acestui varf : daca avarf/0! inseamna canodurile varf si / sunt adiacente. Pentru ca nodul / sa fie adaugat in coada trebuie ca

nodul sa nu fi fost vizitat : viz/0-

4include5fstream.67

4include5conio.67

int a!-!-,c"-,viz!-*

int n,m,prim,ultim,varf*

void bf8iterativ()//parcurgerea in latime9int /*

6ile(prim50ultim)

9varf0cprim*

for(/0!*/50n*/;;)

if(avarf/00!


3/13

9ultim;;*

cultim0/*

viz/0!*=

prim;;*

=

=

void main()

9clrscr()*

int x,>*

fstream f* ??memorare graf in matrice de adiacenta

f.open(@muc6ii.txt@,ios::in)*

f77n77m*

for(int i0!*i50m*i;;)

9f77x77>*

ax>0a>x0!*

=

cout55@matricea de adiac @55endl*// afisare matrice de adiacenta

for( i0!*i50n*i;;)

9for(int 0!*50n*;;)

cout55ai55@ @*

cout55endl*

=

int nd*

prim0ultim0!*

cout55@nodul de inceput0@*

cin77nd* // nodul de la care se porneste parcurgerea

viznd0!*

cprim0nd*

bf8iterativ()*

for(i0!*i50ultim*i;;) //afisarea cozii

cout55ci55@ @*

getc6()* =

1arianta recursiva de parcurgere se obtine modificand functia de parcurgere iterativa

adaugand conditia necesara autoapelului:

void bf8recursiv() ??parcurgerea in latime


4/13

9int /*

if(prim


5/13

}

prim;;*//avansez la urmatorul nod din coada

}

=

void afisare(int nr8nod)

9nod Ap0Lnr8nod*

if(p00-)

cout55nr8nod55@ este izolat @55endl*

else

9cout55@lista vecinilor lui @55nr8nod55endl*

nod Ac0p*

6ile(c)

9cout55c7nd55@ @*

c0c7next*=

cout55endl*=

=

void main()

9fstream f*

int i,*

nod Ap,AB*

f.open(@muc6ii.txt@,ios::in)*

clrscr()*f77n77m*

6ile(f77i77)

9p0ne nod*

p7nd0*

p7next0Li*

Li0p*

B0ne nod*

B7nd0i* B7next0L*

L0B*

=

f.close()*


6/13

cout55endl55@listele de adiacente @*

for(i0!*i50n*i;;)

afisare(i)*

int ndr*cout55endl55@nodul de inceput @*

cin77ndr*

vizndr0!*

prim0ultim0!*

prim0ndr*

cout55endl55@parcurgere in latime @55endl*

bfi8lis()*

for(i0!*i50ultim*i;;)

cout55i55@ @*

getc6()*

=

Functia recursiva

void bfr8lis()

9int varf,nr*

nod Ap*

if(prim50ultim)

9varf0prim* p0Lvarf*?? se parcurge lista elementelor din varful cozii

6ile(p)

9nr0p7nd*

if(viznr00-)??numai daca nu a fost vizitat

9ultim;;*??maresc coada

ultim0nr*??il adaug in coada

viznr0!*=*??il marc6ez ca fiind vizitat

p0p7next*=

prim;;* ??avansez la urmatorul nod din coada

bfr8lis()* =

=

Aplicatii

!.'a se parcurga graful in latime pornind pe rand de la toate varfurile

". 'a se determine daca pornind de la nodul x se poate aunge la nodul >


7/13

$. 'a se determine daca se poate parcurge pornind de la un nod tot graful

#. Cntre n firme sunt stabilite relatii de colaborare (se cunosc perec6ile de firme care colaboreaza). 'a se

determine lungimea minima a lantului de intermediari pentru ca firma x sa colaboreze

cu firma >

x pt x0& si > 0$ . E sulutie pt lantul de lungime minima va fi: & " $. Lungimea este "

. Gn graf neorientat este bipartit daca exista o partitie a multimii nodurilor in doua

multimi H si I astfel incat oricare doua varfuri din aceeasi multime sa nu fie

adiacente. 'a se scrie un program care verifica daca un graf este bipartit si in caz

afirmativ sa se tipareasca multimile H si I


8/13

Cn ex din figura o solutie este: H: !, #,

I: ", $, &, J,

E solutie de rezolvare porneste de la parcurgerea pe rand in latime o

grafului incepand de la primul nod.

'e obtine o prima coada: c!, $, J, #, " apoi coada 0, &, K.

Pentru prima coada se parcurg elementele din c si se marc6eaza sc/ si sc cu

valori diferite (! si ! ) daca ac/c0!. Daca nu este posibil inseamna ca graful

nu este bipartit. La fel se procedeaza si cu cea de a doua coada etc.

'e parcurge ! care se marc6eaza cu !. %odurile adiacente $ si J se marc6eaza cu !.

Hpoi $ si care este adiacent cu #. Deci se marc6eaza # cu !.

Pentru nodul J nu mai sunt noduri adiacente (doar ! care a fost dea parcurs).

'e aunge la nodul # care este vecin cu " . 'e marc6eaza " cu !

La fel se procedeaza cu coada 0,&, K. 'e marc6eaza cu ! si & si K cu !.

E solutie de implementare:

4include5fstream.67

4include5conio.67

int a"-"-,c"-,viz"-*

int s"-*

int n,m,prim,ultim,varf*

void bf8iterativ() ??parcurgerea in latime

9int /*

6ile(prim50ultim)


9/13

9varf0cprim*

for(/0!*/50n*/;;)

if(avarf/00!*

ax>0a>x0!*

=

cout55@matricea de adiac @55endl* ?? afisare matrice de adiacentafor( i0!*i50n*i;;)

9for(int 0!*50n*;;)

cout55ai55@ @*

cout55endl*

=

int nd,/*

int o/0!*

for(nd0!*nd50n*nd;;) if(viznd00-)

9for(/0!*/50n*/;;) ??golesc coada si viz

9c/0-*

viznd0-*

=

prim0ultim0!*


10/13

viznd0!*

cprim0nd*

bf8iterativ()*

cout55endl*

for(int /0!*/50ultim!*/;;)

for(int 0/;!*50ultim*;;) if(ac/c00!)

if(sc/00-


11/13

Parcurgerea grafurilor in a!ancime (!ept" first)

Parcurgerea unui graf in adancime se face prin utilizarea stivei (alocate implicit prin

subprograme recursive).

Pentru fiecare nod se parcurge primul dintre vecinii lui neparcursi inca

Dupa vizitarea nodului initial x!, se exploreaza primul nod adiacent lui fie acesta x ",

se trece apoi la primul nod adiacent cu x" si care nu a fost parcurs inca , s.a.m.d.Fiecare nod se parcurge cel mult odata (daca graful nu este conex nu se vor putea

parcurge toate nodurile)

De exemplul pentru garful din figura de mai os, se va proceda in felul urmator:

se porneste din nodul !, (se poate incepe de la oricare alt nod)

se exploreaza in vontinuare primul vecin al acestuia acestuia : nodul ",

se obtine 1,2

dupa care din " se exploreaza un nod adiacent cu acesta si care nu a fost vizitat : $.

( %odul ! nu se mai viziteaza odata)

se obtine 1,2,3

In continuare ar trebui sa se parcurga vecinul lui 3 nevizitat : 4

se obtine 1, 2, 3, 4

Pentru nodul # ar trebui sa se parcurga primul sau vecin neparcurs (nodul ! dar acesta

a fost dea parcurs. 'i nodul $ a fost parcurs. Din # nu mai avem ce vizita si se trece

la nivelul anterior din stiva, la nodul $ :


12/13

1, 2, 3, 4 Se parcurge vecinul sau nevizitat, nodul 5 .

SE obtine : 1, 2, 3, 4 , 5.%odul $ nu mai are vecini nevizitati si se trece pe nivelul anterior din stiva, nodul

" : 1, 2, 3, 4 , 5. Nici acesta nu mai are vecini nevizitati si se trecepe nivelul anterior la nodul 1: 1, 2, 3, 4 , 5. um nici acesta nu mai arevecini nevizitati se inc6eie algoritmul.

%odul & ramane nevizitat.

Algoritmul

+raful se va memora utilizand matricea de adiacenta a!-!-pentru a nu parcurge un nod de doua ori se va folosi un vector boolean vizcare va

retine :

viz/0- daca nodul / nu a fost vizitat inca

viz/0! daca nodul / a fost vizitat

ca si la parcurgerea in latime vecinii unui nod se 2 cauta 3 pe linia acestui nod : daca

anod/0! inseamna ca nodurile nod si / sunt adiacente. Pentru ca nodul / sa fie fie

parcurs trebuie ca nodul sa nu fi fost vizitat : viz/0-

4include5fstream.67

4include5conio.67int a"-"-,n,m,viz!--,gasit*

void dfmr(int nod)

9

cout55nod55@ @*

viznod0!*

for(int /0!*/50n*/;;)

if(anod/00!


13/13

if(f)

cout55@o/@55endl*

else

cout55@eroare la desc6idere de fisier@*

f77n77m*

for(int i0!*i50m*i;;) 9f77x77>*

ax>0a>x0!*=

cout55endl55@matricea de adiacente@55endl*

for(i0!*i50n*i;;)

9for(0!*50n*;;)

cout55ai55@ @*

cout55endl*=

cout55endl55@parcurgere in adancime incepand de la varful !@55endl*

dfmr(!)*

getc6()*=

Aplicatii

!.'a se parcurga graful in adancime pornind pe rand de la toate varfurile

". 'a se determine daca pornind de la nodul x se poate aunge la nodul >

$. 'a se determine daca se poate parcurge pornind de la un nod tot graful

parcurgerea grafurilor def, teoreme, cod

Documents