Parcurgerea Grafurilor

INTRODUCERE

Graful este larg utilizat în domeniile: ciberneticii, matematicii, cercetărilor operaționale în vederea optimizării diferitelor activități economice, chimiei pentru descrierea structurii cristalelor, rețelelor de transport de toate tipurile pentru optimizarea traseelor, circuitelor electrice pentru simularea funcționări corecte, inteligenței artificiale și nu în ultimul rând în domeniul analizei aplicațiilor software.

Scurt istoric:

1736: Euler publică ,,Cele 7 poduri din Königsberg" – prima lucrare de Teoria Grafurilor.

Ulterior: formula lui Euler, care indică relația dintre numărul de muchii, noduri si fețe ale unui poliedru convex – rezultat generalizat de Cauchy și L'Huillier – studiul topologiilor și al unor clase speciale de grafuri.

1852: De Morgan formulează Conjectura colorării hărții cu 4 culori: patru este numărul minim de culori necesare pentru a putea colora orice hartă astfel ca țările cu granița comună să aibă culori diferite.

1969: Heesch publică o metodă de rezolvare

1976: demonstrație generată de calculator, implementată de K. Appel și W. Haken.

1878: Cuvântul graf este folosit pentru prima oară de Sylvester într-o publicație din Nature.

1936: D. König publică prima carte despre teoria grafurilor

În general, pentru situațiile care necesită la rezolvare un oarecare efort mintal (și un caz tipic este cel al celor din economie), se caută, în primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o privire (pe cât posibil) și prin care să se evidențieze cât mai clar toate aspectele acesteia.

În acest scop se folosesc imagini grafice gen diagrame, schițe, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea sistemelor și situațiilor complexe. În general, vom reprezenta componentele acestora prin puncte în plan iar relațiile (legăturile, dependențele, influențele etc) dintre componente prin arce de curbă cu extremitățile în punctele corespunzătoare. Între două puncte pot exista unul sau mai multe segmente (în funcție de câte relații dintre acestea, care ne interesează, există) iar segmentelor li se pot asocia sau nu orientări (după cum se influențează cele două componente între ele), numere care să exprime intensitatea relațiilor dintre componente etc.

Este evident, totuși, că această metodă are limite, atât din punct de vedere uman (prea multe puncte și segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care a fost creat – claritatea și simplitatea reprezentării, aceasta devenind neinteligibilă) cât și din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, alături de expunerea naiv-intuitivă a ceea ce este un graf, dată mai sus, se impune atât o definiție riguroasă cât și alte modalități de reprezentare a acestora, adecvate în general rezolvărilor matematice.

Grafurile sunt utile pentru a modela diverse probleme și se regăsesc implementați în multiple aplicații practice:

Rețele de calculatoare (ex: stabilirea unei topologii fără bucle)

Pagini Web (ex: Google PageRank)

Rețele sociale (ex: calcul centralitate)

Harți cu drumuri (ex: drum minim)

Modelare grafica (ex: prefuse, graph-cut)

CAPITOLUL I

NOȚIUNI FUNDAMENTALE DIN TEORIA GRAFURILOR

Se numește graf neorientat o pereche ordonată de mulțimi G=(X, U), unde: X ={ x1,x2, x3, …, xn} este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U o mulțime finită de perechi neordonate de forma (xi, xj), unde ij și xi, xjX, numite muchii. O muchie unește două noduri.

X se numește mulțimea nodurilor sau vârfurilor, iar U se numește mulțimea muchiilor grafului G.

Un vecin al unui vârf este orice vârf care este adiacent lui în graf. O muchie uU este deci o submulțime {x, y} de vârfuri distincte din X și se notează u = [x, y]. x și y sunt adiacente în G, iar u și x sunt incidente la fel ca u și y. x și y se numesc extremitățile muchiei u.

Dacă u1 și u2 sunt 2 muchii care au o extremitate comună, ele se numesc incidente. Mulțimea muchiilor are proprietatea de simetrie, deoarece [x, y]U dacă și numai dacă [y,x]U.

Exemplu: Fie G = (X, U), astfel încât X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, iar U = {[1, 5], [3, 7], [4, 6], [9, 8], [10, 2], [1, 2], [9, 4], [1, 10], [6, 8]}.

Se numește graf orientat o pereche ordonată de mulțimi notată G=(V, U), unde:

V: este o mulțime, finită si nevidă, ale cărei elemente se numesc noduri sau vârfuri;

U: este o mulțime, de perechi ordonate de elemente distincte din V, ale cărei elemente se numesc arce.

Exemplu de graf orientat reprezentat textual:

G=(V, U) unde: V={ 1,2,3,4}

U={(1,2), (2,3), (1,4), (4,1)}

Exemplu de graf orientat reprezentat grafic:

Gradul unui vârf x este numărul muchiilor incidente cu x. Se notează cu d (x) (d = degree).

Un vârf care are gradul 0 (deci pentru care nu există vreo muchie incidentă cu el) se numește vârf izolat. Un vârf care are gradul 1 (deci care este incident cu o singură muchie) se numește vârf terminal.

Exemplu: Pentru graful G definit anterior, d (11) = 0, deci vârful 11 este izolat.

Fie un graf neorientat cu n noduri și m muchii. Dacă notăm cu d1, d2, d3, …, dn gradele celor n noduri, atunci avem relația:

d1 + d2 + d3 + … + dn = 2m

Se numește lanț L = [x0, x1, …, xn] o succesiune de vârfuri cu proprietatea că oricare două vârfuri consecutive sunt adiacente.

Vârfurile x0 și xn se numesc extremitățile lanțului. Numărul n se numește lungimea lanțului și este numărul de muchii din care este format.

Lanțul care conține numai vârfuri distincte, două câte două, este lanț elementar.

Lanțul care conține numai muchii distincte este lanț simplu. Dacă muchiile unui lanț nu sunt distincte se numește lanț compus.

O matrice pătratică de ordin n se numește matricea lanțurilor, dacă:

1, dacă există lanț de la i la j

li,j =

0, în caz contrar

Exemplu: Fie G = (X, U), astfel încât X = {1, 2, 3, 4, 5, 6}, iar U = {[1, 2], [2, 3], [3, 4], [3, 5], [4, 5], [5, 6]}.

Un lanț pentru care x0 = xn (primul nod coincide cu ultimul) se numește ciclu. Dacă toate vârfurile unui ciclu, cu excepția primului și ultimului, sunt distincte, ciclul se numește elementar.

Lungimea unui ciclu nu poate fi 2.

Un ciclu se numește par dacă lungimea sa este pară și impar în caz contrar.

Exemplu: În graful din figura anterioară lanțul 3, 4, 5, 3 este un ciclu elementar impar. Lanțul 2, 5, 3, 4, 5, 6, 2 este un ciclu par, dar nu este elementar.

Dacă U = atunci graful G = (X, U) se numește graf nul, și reprezentarea lui în plan se reduce la puncte izolate.

Un graf parțial al grafului G = (X, U) este un graf G1 = (X, V) astfel încât VU, adică G1 are aceeași mulțime de vârfuri ca G iar mulțimea de muchii V este chiar U sau o submulțime a acesteia.

Un graf parțial al unui graf se obține păstrând aceeași mulțime de vârfuri și eliminând o parte din muchii. Graful parțial G1 este indus de mulțimea de muchii V.

Exemplu: Pentru graful G definit anterior G1 = (X, V), unde V = {[1, 5], [4, 6], [10, 2]}, este un graf parțial.

Un subgraf al grafului G = (X, U) este un graf H = (Y, V) astfel încât YX, iar V conține toate muchiile din U care au ambele extremități în Y. Subgraful H este indus sau generat de mulțimea de vârfuri Y.

Exemplu: Pentru graful G definit anterior, dacă Y = {1, 2, 3, 7, 10} și V = {[1, 2], [1, 10], [2, 10], [3, 7]}, atunci H = (Y, V) este un subgraf al grafului G.

Un subgraf al unui graf se obține eliminând o parte din vârfuri și toate muchiile incidente cu acestea.

Un graf fără cicluri se numește graf aciclic. Un graf aciclic și conex este un arbore.

În cazul grafului aciclic fiecare componentă conexă este un arbore. Un graf neorientat aciclic, care s-ar putea să nu fie conex, se numește pădure.

Exemplu: Graful de mai jos este aciclic și formează o pădure. Cele 3 componente conexe sunt

arbori.

Se numește graf complet cu n vârfuri un graf cu proprietatea că oricare două noduri distincte sunt adiacente. Un graf complet cu n vârfuri se notează Kn.

Exemplu: Graful definit mai jos este complet și se notează cu K5.

Într-un graf complet, gradul oricărui nod este n – 1, pentru că din/în fiecare nod pleacă/sosesc n – 1 muchii.

Într-un graf complet, avem relația: m = n(n – 1)/2 = (numărul de submulțimi cu 2 elemente ale mulțimii celor n noduri), unde m este numărul de muchii, iar n numărul de noduri.

Un graf G = (X, U) se numește bipartit dacă există 2 mulțimi nevide A și B astfel încât X = A B, A B = și orice muchie u a lui G are o extremitate în A iar cealaltă în B. Mulțimile A și B formează o partiție a lui X.

Un graf este bipartit dacă și numai dacă nu conține cicluri de lungime impară.

Exemplu: A = {1, 3, 4} și B = { 2, 5, 6, 7}

Un graf bipartit se numește complet dacă pentru xA și yB, în G muchia [x, y]. Notația este Kp,q unde p și q sunt elementele mulțimii A și respectiv ale mulțimii B.

Exemplu: K3,4 este:

Un graf în care toate nodurile au același grad se numește graf regulat.

Exemplu: Graful definit mai jos este regulat.

Un graf se numește graf conex dacă pentru oricare două vârfuri x și y diferite ale sale, există un lanț care le leagă, adică x este extremitatea inițială și y este extremitatea finală.

Un graf cu un singur nod este, prin definiție, conex.

Se numește componentă conexă a unui graf G = (X,U) un subgraf H = (Y, V), conex, al lui G care are proprietatea că nu există nici un lanț în G care să lege un vârf din Y cu un vârf din X – Y.

Un graf este conex dacă admite o singură componentă conexă.

Exemplu: Graful definit mai jos are o singură componentă conexă și în consecință este conex.

Un graf este biconex dacă este conex și pentru orice vârf eliminat subgraful generat își păstrează proprietatea de conexitate.

Exemplu: Graful definit mai jos este biconex.

Un multigraf seamănă cu un graf neorientat, însă poate avea atât muchii multiple între vârfuri cât și autobucle. Un hipergraf seamănă cu un graf neorientat, dar fiecare hipermuchie, în loc de a conecta două vârfuri, conectează o submulțime arbitrară de vârfuri.

Costul unui graf este o funcție definită pe mulțimea muchiilor grafului cu valori în mulțimea numerelor reale. Un graf notat cu o astfel de funcție este notat sub forma: G = (X, U, c).

Exemplu: G = ( X , U , c) este graful:

Se numește ciclu hamiltonian un ciclu elementar care trece prin toate vârfurile grafului. Un graf care admite un ciclu hamiltonian se numește graf hamiltonian.

Fie G = (X,U) un graf neorientat și un lanț elementar care trece prin toate nodurile grafului [x0, x1, …, xn]. Dacă d(x1) + d(xn)≥n atunci graful este hamiltonian.

Fie G = (X,U) un graf neorientat cu n noduri. Dacă pentru orice pereche de noduri neadiacente xixj, avem relația d(xi) + d(xj)≥n atunci graful este hamiltonian.

Dacă G = (X,U) este un graf neorientat cu n noduri și gradul oricărui vârf este mai mare sau egal n/2, atunci G este hamiltonian.

Un graf G este hamiltonian dacă are n≥3 vârfuri și gradul oricărui vârf verifică inegalitatea: d(x)≥n/2.

Exemplu: 1 , 2 , 3 , 9 , 8, 7, 5, 6, 4, 1 este ciclu hamiltonian.

Un lanț al unui graf care conține fiecare muchie o dată și numai o dată se numește lanț eulerian. Dacă x0 = xn și lanțul este eulerian atunci, ciclul respectiv se numește ciclu eulerian.

Un graf care conține un ciclu eulerian se numește graf eulerian.

Dacă este eulerian nu înseamnă că nu are vârfuri izolate.

Exemplu: 1 , 2 , 4 , 6 , 5 , 7, 8, 3, 9, 8, 5, 2, 3, 4, 1 este ciclu eulerian.

Un graf G = (X,U), fără vârfuri izolate, este eulerian dacă și numai dacă este conex și

gradele tuturor vârfurilor sale sunt numere pare.

Reprezentarea grafurilor

Reprezentare grafuri neorientate

Forma uzuală de reprezentare a grafurilor neorientate este prin asocierea unei valori logice pentru existența sau nu a unei muchii între două noduri.

Astfel, dacă G = (X,U) este un graf neorientat, atunci pentru orice x, y∈ X , considerăm

1 pentru x, yU

mx,y =

0 pentru x, yU

Fie G  X ,U  un graf neorientat cu X  n și presupunem că X x1 , x2 ,…, xn Definim matricea definită prin . Matricea AG se numește matricea de adiacență asociată grafului G.

Exemplu. Fie G = ( X,U ) un graf neorientat cu X = {1, 2,3,4,5} și

U = {{1,2},{1, 4},{2,3},{2, 4},{3,5},{4,5}}

Graful are imaginea:

Construim tabelul definiție elementelor m( x, y) și obținem:

Matricea de adiacență este astfel:

Observație: Pe diagonala principală toate elementele sunt 0.

Matricea este simetrică față de diagonala principală, deci: a[i,j] = a[j,i].

Dacă G = ( X,U ) este un graf neorientat, atunci pentru orice x, y∈ X , considerăm

1 L =[x = x0,x1,…,xr = y] în G

=

0 altfel

Fie G  X ,U  un graf neorientat cu X  n și presupunem că X x1 , x2 ,…, xn Definim matricea definită prin . Matricea LG se numeste matricea lanțurilor grafului G.

Exemplu. Se consideră graful din exemplul dat ;i dorim să-i scriem matricea lanțurilor. Pentru aceasta se observă că avem lanțurile {1,2}, {1,2,3} , {1,4}, {1,4,5} , {2,3} , {2, 4} , {2,3,5} , {3,5, 4} , {3,5} si {4,5} care demonstrează că există lanțuri între oricare două vârfuri ale grafului (graful este conex). Astfel, matricea lanțurilor va fi

Reprezentare grafuri orientate

Fie G = (X,U) este un graf orientat cu X  n și presupunem că X x1 , x2 ,…, xn

Matricea dată prin

1 pentru U

= orice

0 pentru U

se numește matricea de adiacență asociată grafului G.

După cum se poate observa, noțiunea este similară celei de la grafurile neorientate. De această dată, însă, matricea de adiacență asociată unui graf nu mai este o matrice simetrică. De asemenea, matricea de adiacență poate conține valori 1 pe diagonala principală, dacă graful orientat conține arce de forma (x, x) ∈U (bucle).

Exemplu. Fie graful G = (X,U) pentru care X = {1,2,3,4,5} și

U={(1, 2),(2,4),(3,1),(3,2),(3, 4),(5,2),(5,5)}.

Graful considerat are următoarea reprezentare:

Matricea de adiacență este:

Fie G  X ,U  un graf neorientat cu X  n și presupunem că X x1 , x2 ,…, xn Matricea definită prin

1 [x1 = y0,y1,…,yr = xj] lanț în G

=

0 altfel

se numeste matricea lanțurilor grafului G.

Matricea lanțurilor se definește, în mod similar, cu cea dată pentru grafurile neorientate și este o matrice simetrică.

CAPITOLUL II

PARCURGEREA GRAFURILOR

Rezolvarea multor probleme de grafuri, presupune parcurgerea lor de la un anumit nod. Pentru explorarea grafurilor, există doua tipuri de algoritmi: de explorare în lățime și de explorare în adâncime. Parcurgerea grafurilor orientate este similară cu a grafurilor neorientate, se ține cont însă de orientare.

2.1. Parcurgerea în lățime (Breadth First Search, BFS):

Căutarea pe lățime este unul din cel mai simpli algoritmi și poate și folositori algoritmi de căutare în grafuri. Se obțin drumurile dintr-un nod sursă către orice nod din graf astfel:

Fiind dat un graf G = (V, E) și un nod sursă s, această căutare va permite explorarea sistematică în G și descoperirea fiecărui nod plecând din s. Totodată, se calculează și distanța de la s la fiecare nod ce poate fi vizitat. În felul acesta se construiește un arbore “pe lățime” cu rădăcina în s ce conține toate nodurile ce pot fi vizitate. Pentru orice nod v, ce poate fi vizitat plecând din s, drumul de la rădăcină la acest nod, drum refăcut din arborele ”pe lățime”, este și cel mai scurt de la s la v, în sensul că acest drum conține cele mai puține muchii. Algoritmul funcționează atât pe grafuri orientate cât și pe cele neorientate.

Numele algoritmului provine din faptul că limita dintre nodurile descoperite și cele nedescoperite, limită pe care o extinde la fiecare pas, este distribuită uniform de-a lungul unei lățimi.

Adică, algoritmul descoperă toate nodurile la o distanță k de s înainte de a descoperi pe cele la distanța k +1.

Pentru a marca nodurile descoperite, algoritmul va colora nodurile cu alb, gri, negru. La început, toate nodurile sunt albe, apoi vor deveni gri, și mai apoi negre. Un nod descoperit pentru prima dată este marcat de algoritm cu o întunecare a culorii (adică de la alb trece la gri și mai apoi negru). Nodurile negre și gri sunt deci, marcate ca descoperite, dar algoritmul le distinge după cum urmează. Dacă (u, v) ∈ E și nodul u este negru, atunci nodul v este fie gri fie negru: toate nodurile adiacente unui nod negru sunt descoperite. Nodurile gri pot avea unele noduri adiacente albe: ele reprezintă frontiera între nodurile descoperite și cele nedescoperite.

Algoritmul de căutare pe lățime construiește un arbore pe lățime cu o rădăcină inițială s, adică nodul sursă. Atunci când este descoperit un nod v (atunci când verificăm lista de adiacență a lui u – un nod deja descoperit), atunci nodul v și muchia (u, v) sunt adăugate arborelui. Vom spune că u este predecesorul sau părintele lui v.

Algoritmul BFS (de căutare pe lățime) are ca intrare graful G = (V, E) reprezentat ca listă de adiacență. Va menține și date adiționale pentru fiecare nod din graf. Culoarea fiecărui nod u ∈ V este stocată în șirul color[u] și predecesorul lui u, în șirul a[u]. Dacă u nu are predecesor (de exemplu u = s sau un nu a fost descoperit încă), atunci a[u] = NIL. Distanța de la sursă la u se poate ține în d[u]. Se poate construi un obiect cu toate aceste date pentru a nu avea trei șiruri adiționale.

Algoritmul este cel de mai jos, unde Q este o structură de tip coadă.

BFS(G, s)

1. for each vertex u ∈ V[G] − {s} do

2. color[u] ← WHITE

3. d[u] ← ∞

4. a[u] ← NIL

5. color[s] ← GRAY

6. d[s] ← 0

7. a[s] ← 0

8. Q ← {s}

9. while Q ≠ 0 do

10. u ← ℎead[Q]

11. for each v ∈ Adj[u] do

12. if color[v] = WHITE then

13. color[v] ← GRAY

14. d[v] ← d[u]+ 1

15. a[v] ← u

16. ENQUEQUE(Q, v)

17. DEQUEQUE(Q)

18. color[u] ← BLACK

Această procedură funcționează astfel: liniile 1-4 inițializează șirurile, fiecare nod având culoarea albă, iar distanțele fiind maxime. Linia 5 va marca sursa ca fiind descoperită, deci gri. Linia 6 inițializează drumul de la sursă la sursă ca fiind 0 și linia 7 marchează faptul că sursa nu are predecesor. Linia 8 inițializează coada Q. Aceasta conține la început doar nodul sursă urmând să adăugam până la sfârșit toate nodurile din graf în Q.

Nucleul algoritmului se găsește între liniile 9-18 și anume bucla while, va itera câtă vreme mai avem noduri gri, ce reprezintă noduri descoperite care au în lista lor de adiacență vecini ce nu au fost încă vizitați. Linia 10 va stabili u ca fiind capul cozii Q. În cadrul for-ului din liniile 11-16 se va lua în considerare fiecare nod adiacent al lui u. În caz că acel nod v nu a fost vizitat algoritmul îl va marca (pe liniile 13-16): prima dată este colorat în gri, distanța lui este cu unu mai mare decât a vecinului u și este marcat ca succesor al lui u.

Atunci când toți vecinii lui u au fost examinați, u este eliminat din coadă și colorat cu negru (adică a fost adăugat deja în arbore și i s-au vizitat toți vecinii). În figura de mai jos este exemplificat acest algoritm pe graful din a).

Din moment ce suma tuturor listelor de adiacență este Ɵ(E), rezultă că cel mai rău caz ar avea un ordin de timp de O(E) pentru parcurgerea listelor.

La explorarea în lățime, după vizitarea vârfului inițial, se explorează toate vârfurile adiacente lui, se trece apoi la primul vârf adiacent și se explorează toate vârfurile adiacente acestuia și neparcurse încă, ș.a.m.d.

Fiecare vârf se parcurge cel mult odată.

De exemplu pentru graful din figura de mai jos, se va proceda în felul următor: se pornește din nodul 1, (se poate începe de la oricare alt nod)

Fig. 2.4

se explorează în continuare vecinii acestuia: nodul 2 si apoi 4,

se obține 1,2,4

Fig. 2.5

după care din 2 se explorează nodul adiacent acestuia 3. Nodul 1 nu se mai vizitează odată

se obține 1,2,4,3

Fig. 2.6

În continuare ar trebui parcurși vecinii lui 4 (1,2,4,3) dar acesta nu mai are vecini nevizitați și se trece la vecinii lui 3: 1,2,4,3 respectiv nodul 5:

se obține 1, 2, 4, 3, 5

Fig. 2.7

Vârful 6 rămâne neparcurs.

Dacă se parcurge graful începând de la vârful 2, soluția este: 2,3,4,5, în timp ce parcurgerea începând cu 4 va reține doar vârful 4.

Implementarea algoritmului

Se va folosi o coadă în care se înscriu nodurile în forma în care sunt parcurse: nodul inițial vârf (de la care se pornește), apoi vârfurile a,b,…, adiacente lui vârf, apoi cele adiacente lui a, cele adiacente lui b,…, ș.a.m.d.

Coada este folosită astfel:

– se încarcă primul vârf în coadă;

– se află toate vârfurile adiacente cu primul nod și se introduc după primul vârf

– se ia următorul nod și i se află nodurile adiacente

– procesul se repetă până când se ajunge la sfârșitul cozii

– Graful se va memora utilizând matricea de adiacenta a[10][10]

– pentru memorarea succesiunii vârfurilor parcurse se va folosi un vector c[20] care va funcționa ca o coadă

– pentru a nu parcurge un vârf de doua ori se va folosi un vector boolean viz[20] care va reține:

– viz[k]=0 dacă vârful k nu a fost vizitat încă

– viz[k]=1 dacă vârful k a fost vizitat

– doua variabile: prim și ultim vor reține două poziții din vectorul c și anume:

– prim este indicele componentei pentru care se parcurg vecinii (indexul componentelor marcate cu roșu în șirurile parcurse anterior ). Prin urmare Vârf=c[prim], este elementul pentru care se determină vecinii (vârfurile adiacente)

– ultim este poziția în vector pe care se va face o nouă inserare în vectorul c (evident, de fiecare dată când se realizează o nouă inserare se mărește vectorul)

– vecinii unui vârf se « caută » pe linia acestui vârf: daca a[varf][k]=1 înseamnă că vârf și k sunt adiacente. Pentru ca vârful k să fie adăugat în coadă trebuie ca vârful să nu fi fost vizitat: viz[k]=0

#include<fstream.h>

#include<conio.h>

int a[10][10],c[20],viz[10];

int n,m,prim,ultim,varf;

void bf_iterativ() //parcurgerea in latime

{int k;

while(prim<=ultim)

{varf=c[prim];

for(k=1;k<=n;k++)

if(a[varf][k]==1&&viz[k]==0) //il adaug pe k in coada daca este vecin pt. varf si nu a fost vizitat

{ultim++;

c[ultim]=k;

viz[k]=1;}

prim++;

}

}

void main()

{clrscr();

int x,y;

fstream f; //memorare graf in matrice de adiacenta

f.open("muchii.txt",ios::in);

f>>n>>m;

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

{f>>x>>y;

a[x][y]=1;

}

cout<<"matricea de adiac "<<endl; // afisare matrice de adiacenta

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

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

cout<<a[i][j]<<" ";

cout<<endl;

}

int nd;

prim=ultim=1;

cout<<"varful de inceput=";

cin>>nd; // varful de la care se porneste parcurgerea

viz[nd]=1;

c[prim]=nd;

bf_iterativ();

for(i=1;i<=ultim;i++) //afisarea cozii

cout<<c[i]<<" ";

getch();

}

Varianta recursivă de parcurgere se obține modificând funcția de parcurgere iterativă adăugând condiția necesară autoapelului:

void bf_recursiv() //parcurgerea in latime

{int k;

if(prim<=ultim)

{varf=c[prim];

for(k=1;k<=n;k++)

if(a[varf][k]==1&&viz[k]==0) //îl adaug pe k în coadă dacă este vecin pentru vârf și nu a fost vizitat

{ultim++;

c[ultim]=k;

viz[k]=1;}

prim++;

bf_recursiv();

}

}

Parcurgerea în lățime a grafurilor memorate prin liste este similară cu diferența că vecinii unui nod adăugat în coadă se caută în lista corespunzătoare lui:

#include<conio.h>

#include<fstream.h>

struct nod

{int nd;

nod *next;};

nod *L[20];

int viz[100]; //marchez cu 1 nodurile vizitate

int m,n;

int prim,ultim,C[100];

void bfi_lis()

{int varf,nr;

nod *p;

while(prim<=ultim)

{varf=C[prim];

p=L[varf]; // se parcurge lista elementelor din varful cozii

while(p)

{nr=p->nd;

if(viz[nr]==0) //numai daca nu a fost vizitat

{ultim++; //maresc coada

C[ultim]=nr; //il adaug in coada

viz[nr]=1;}; //il marchez ca fiind vizitat

p=p->next;

}

prim++; //avansez la urmatorul varf din coada

}

}

void afisare(int nr_nod)

{nod *p=L[nr_nod];

if(p==0)

cout<<nr_nod<<" este izolat "<<endl;

else

{cout<<"lista vecinilor lui "<<nr_nod<<endl;

nod *c=p;

while(c)

{cout<<c->nd<<" ";

c=c->next;}

cout<<endl;}

}

void main()

{fstream f;

int i,j;

nod *p,*q;

f.open("muchii.txt",ios::in);

clrscr();

f>>n>>m;

while(f>>i>>j)

{p=new nod;

p->nd=j;

p->next=L[i];

L[i]=p;

}

f.close();

cout<<endl<<"listele de adiacente ";

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

afisare(i);

int ndr;

cout<<endl<<"nodul de inceput ";

cin>>ndr;

viz[ndr]=1;

prim=ultim=1;

C[prim]=ndr;

cout<<endl<<"parcurgere in latime "<<endl;

bfi_lis();

for(i=1;i<=ultim;i++)

cout<<C[i]<<" ";

getch();

}

Functia recursiva:

void bfr_lis()

{int varf,nr;

nod *p;

if(prim<=ultim)

{varf=C[prim];

p=L[varf];// se parcurge lista elementelor din varful cozii

while(p)

{nr=p->nd;

if(viz[nr]==0)//numai daca nu a fost vizitat

{ultim++;//maresc coada

C[ultim]=nr;//il adaug in coada

viz[nr]=1;};//il marchez ca fiind vizitat

p=p->next;}

prim++; //avansez la urmatorul nod din coadă

bfr_lis();

}

}

2.2. Parcurgerea în adâncime (Depth First Search, DFS):

Spre deosebire de algoritmul BFS, în căutarea în adâncime muchiile sunt explorate în felul următor: dacă ajunge în nodul v, vor fi explorate acele muchii care sunt conectate la v dar care încă nu au fost descoperite. Atunci când toate muchiile lui v au fost explorate, căutarea se retrage pentru a explora muchiile ce pleacă din nodurile adiacente lui v. Acest proces continuă până când am descoperit toate nodurile ce pot fi vizitate plecând de la sursa s. Dacă rămân noduri nedescoperite, atunci unul din ele poate fi stabilit ca sursă, și atunci, căutarea este repetată din acea sursă.

Ca și în BFS, atunci când un nod v este descoperit în timpul unei verificări a listei de adiacență a unui nod deja descoperit, u, algoritmul va memora acest nod și va spune că u este predecesorul lui v și anume a[v] = u. Spre deosebire de BFS, a cărui graf de predecesori forma un arbore, acum graful de predecesori poate fi compus din mai mulți arbori, deci o pădure.

Ca și în BFS, nodurile sunt colorate în timpul căutării pentru a marca starea lor. Fiecare nod este inițial alb, apoi este marcat cu gri dacă este descoperit, și mai apoi cu negru dacă este terminat, adică lista de adiacența a fost complet examinată.

Pe lângă crearea de pădure de adâncime, algoritmul va pune un marcaj de timp pe fiecare nod.

Fiecare nod, are două marcaje de timp, primul d[v] denotă faptul că v a fost descoperit și colorat gri, iar al doilea marcaj memorează când examinarea listei de adiacență s-a încheiat, și anume când v a fost colorat în negru. Aceste marcaje pot fi folosite în mulți algoritmi cu grafuri și sunt o informație folositoare. Procedura DFS de mai jos va prinde momentul descoperirii lui u în variabila d[u] și momentul examinării tuturor vecinilor lui în f[u].

Pentru orice nod u avem relația d[u] < f[u].

Nodul u este alb înainte de timpul d[u], gri înainte de f[u] și negru după f[u]. Pentru marcarea timpului vom folosi variabila time.

DFS(G)

1. for each vertex u ∈ V[G] do

2. color[u] ← WHITE

3. a[u] ← NIL

4. time ← 0

5. for each vertex u ∈ V[G] do

6. if color[u] = WHITE then

7. DFS − VISIT(u)

DFS − VISIT(u)

1. color[u] ← GRAY

2. d[u] ← time ← time + 1

3. for each v ∈ Adj[u] do

4. if color[v] = WHITE then

5. a[v] ← u

6. DFS+VISIT(v)

7. color[u] ← BLACK

8. f[u] ← time ← time + 1

Procedura DFS funcționează astfel: liniile 1-3 vor color toate nodurile în alb și marca toți predecesorii cu NIL. Linia 4 va reseta contorul de timp global. Liniile 5-7 verifică fiecare nod din ∈, iar când este găsit unul alb, atunci are loc apelul DFS-VISIT pentru acel nod. De fiecare dată când este apelat DFS-VISIT pentru un nod u, nodul devine rădăcină pentru un nou arbore și ii va fi asociat un timp de descoperire d[u] și un timp de încheiere a căutării pentru acel nod f[u].

La fiecare apel DFS-VISIT(u), nodul u este inițial alb. Linia 1 din această procedură va colora u cu gri, linia 2 va contoriza timpul descoperirii.

Liniile 3-6 examinează fiecare nod v adiacent lui u, și va vizita recursiv acel v care este alb.

Ultimele linii 7-8 colorează nodul curent u în negru și marchează timpul respectiv.

Mai jos avem un exemplu ilustrativ pentru acest tip de parcurgere.

Vom mai introduce două variabile care se vor dovedi utile în unele aplicații:

tDesc (timpul descoperirii): pasul la care se marchează nodul cu gri;

tFin (timpul final): pasul la care se marchează nodul cu negru.

Și la DFS, ca și la BFS, în urma parcurgerii se obțin arbori. Aceștia se numesc arbori de adâncime. Spre exemplu:

Evident, pe acest arbore s-ar putea adăuga și muchiile pe care nu le-am folosit în parcurgere, dar l-ar face să nu mai fie arbore. Totuși, în cazul grafurilor orientate, și aceste muchii au o semnificație specială.

Am transformat graful din exemplul precedent într-unul orientat și i-am mai adăugat câteva noduri. Și de data asta i-am figurat toate muchiile. Acestea vor fi:

muchii înainte: muchia (1,4);

muchii înapoi: muchia (3,1);

muchii de traversare: muchia (9,1).

Un alt exemplu pentru grafuri neorientate

Se pornește de la un nod oarecare x.

Se alege primul vecin al lui x care nu a fost încă vizitat.

Pentru nodul ales se reia procedeul.

Dacă un nod nu are nici un vecin nevizitat se revine la nodul vizitat anterior acestuia.

Structuri de date necesare implementării:

Matrice de adiacență (sau alte variante): a

Stivă: s (in care se memorează nodurile in ordinea parcurgerii)

Dacă se implementează varianta recursivă se va folosi stiva procesorului

Vectorul nodurilor vizitate: v

int a[20][20],u;

int v[20];

void DF(int x){

 cout<<x<<" ";

 v[x]=1;

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

  if(a[x][i] && !v[i])

   DF(i);

}

Pentru grafuri orientate

x = 10

10, 4, 2, 1, 3, 6, 8, 7, 9

Parcurgerea este similară, punându-se condiția de parcurgere a tuturor vecinilor unui nod indiferent de sens.

Aplicație la metodele de parcurgere.

1. Parcurgerea unui graf in adâncime pentru determinarea ciclurilor care conțin un nod specificat

#include <stdio.h>

#include <conio.h>

#define n 6

int m[n][n]={{0,1,0,0,0,1},

{0,0,1,0,0,0},

{0,1,0,1,0,1},

{1,0,0,0,0,1},

{0,0,1,0,0,0},

{0,1,0,0,1,0}};

int s[n];

int varf=0;

int verific(int c) //se verifica daca nodul a fost inclus in stiva

{ for (int i=0;i<varf;i++)

if (s[i]==(c)) return 1; //nodul exista in stiva

return 0; //nodul nu exista in stiva

}

void afisare()

{ printf("\n Solutie: ");

for (int i=0;i<varf;i++)

printf(" %d",s[i]); }

void main()

{ int nod; //nod-nodul de la care incepe parcurgerea

int rand,col;

int parcurs; //parcurs=1 – s-a parcurs intreg graful

int extrag; //extrag -var. folosita pentru extragerea unui elem din stiva

clrscr();

do

{ puts("Introdu numarul nodului:");

scanf("%d",&nod);

if (nod>n)

{ puts("Valoare prea mare");

getch(); }

} while (nod>n-1);

s[varf]=nod; varf++; //se depune prima valoare in stiva

rand=nod; col=0;

parcurs=0;

while (parcurs==0)

{ while ((m[rand][col]==0)&&(col<n))

col++;

if (col<n)

{ if (!verific(col))

{ s[varf]=col; //se adauga nodul in lista

varf++;

rand=col;

col=0; }

else

{ if (col==nod)

afisare();

col++; }

}

else //ptr nodul din varful stivei s-au verificat toate arcele, deci se extrage din stiva

{ extrag=s[varf-1];

varf–;

if (extrag==nod)

parcurs=1; //s-au extras toate nodurile din stiva-se incheie parcurgerea grafului

else //se trateaza in continuare nodul ramas in varf

{ col=extrag+1;

rand=s[varf-1]; }

}

}

}