Parcurgerea grafurilor

PARCURGEREA GRAFURILOR

Parcurgerea grafurilor

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. Parcurgerea grafurilor orientate este similara cu a grafurilor neorientate, se tine cont insa de orientare.

1. Parcurgerea in latime (Breadth First Search, BFS):

Parcurgerea in latime foloseste o coada (Q) intr-un mod asemanator celui folosit de algoritmul AC- Initial in aceasta coada se gaseste doar nodul sursa. Vizitand pe rand vecinii sai ii adaugam si pe ei in coada. La sfarsit, dupa ce nu mai sunt vecini ai sursei nevizitati, scoatem nodul sursa din coada.

Pentru fiecare din nodurile prezente in coada, aplicam procedura de mai sus. Atentie insa: vizitand vecinii unui nod trebuie sa verificam ca acestia nu au mai fost deja vizitati (adica sunt inca albi).

. . .

In afara de coada q mai sunt necesare sau utile cateva structuri de date.

a) Putem diferentia intre nodurile nevizitate, cele asezate in coada si cele complet prelucrate printr-un vector denumit culoare:

c[nod] = alb, daca nodul nu a fost vizitat

gri, daca nodul a fost vizitat si asezat in q

negru, daca nodul a fost prelucrat si scos din q

b) Un vector d (distanta) care sa retina distanta (in numar de muchii) fata de sursa se poate dovedi util in unele probleme.

c) Vectorul de parinti p este necesar pentru a reface drumul de la sursa la un alt nod dupa parcurgere.

Algoritmul conform specificatiilor de mai sus: 

// = = = = = initializari = = = = = = =

pentru fiecare nod u

c[sursa] = gri;

d[s] = 0;

q = ;

// = = = = = = algoritm = = = = = = =

cattimp (q nu este vida)

c[v] = negru;

}

Obs: Pentru ca muchiile care unesc noduri deja gri nu sunt practic folosite, se intuieste asezarea muchiilor folosite intr-un graf conex si fara cicluri (adica un arbore):

Obs: Daca graful are mai multe componente conexe, algoritmul, in forma data aici, va parcurge doar componenta din care face parte nodul sursa. Pe grafuri alcatuite din mai multe componente conexe se vor obtine astfel mai multi arbori, cate unul pentru fiecare componenta.

La explorarea in latime, dupa vizitarea varfului initial, se exploreaza toate varfurile adiacente lui, se trece apoi la primul varf adiacent si se exploreaza toate varfurile adiacente acestuia si neparcurse inca, s.a.m.d.

Fiecare varf se parcurge cel mult odata.

De exemplu pentru graful din figura de mai jos, se va proceda in felul urmator:

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

se exploreaza in continuare vecinii acestuia: nodul 2 si apoi 4,

se obtine 1,2,4

dupa care din 2 se exploreaza nodul adiacent acestuia Nodul 1 nu se mai viziteaza odata

se obtine 1,2,4,3

In continuare ar trebui parcursi vecinii lui 4 (1,2,4,3) dar acesta nu 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

Varful 6 ramane neparcurs.

Daca se parcurge graful incepand de la varful 2, solutia este: 2,3,4,5, in timp ce parcurgerea incepand cu 4 va retine doar varful 4

Implementarea algoritmului

Se va folosi o coada in care se inscriu nodurile in forma in care sunt parcurse: nodul initial varf (de la care se porneste), apoi varfurile a,b,, adiacente lui varf, apoi cele adiacente lui a, cele adiacente lui b,, s.a.m.d.

Coada este folosita astfel:

- se incarca primul varf in coada;

- se afla toate varfurile adiacente cu primul nod si se introduc dupa primul varf

- se ia urmatorul nod si i se afla nodurile adiacente

- procesul se repeta pana cand se ajunge la sfarsitul cozii

- Graful se va memora utilizand matricea de adiacenta a[10][10]

- pentru memorarea succesiunii varfurilor parcurse se va folosi un vector c[20] care va functiona ca o coada

- pentru a nu parcurge un varf de doua ori se va folosi un vector boolean viz[20] care va retine:

- viz[k]=0 daca varful k nu a fost vizitat inca

- viz[k]=1 daca varful k 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 Varf=c[prim], este elementul pentru care se determina vecinii (varfurile 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 unui varf se « cauta » pe linia acestui varf: daca a[varf][k]=1 inseamna ca varf si k sunt adiacente. Pentru ca varful k sa fie adaugat in coada trebuie ca varful sa 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

prim++;

}

void main()

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

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

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 recursiva de parcurgere se obtine modificand functia de parcurgere iterativa adaugand conditia necesara autoapelului:

void bf_recursiv() //parcurgerea in latime

prim++;

bf_recursiv();

}

Parcurgerea in latime a grafurilor memorate prin liste este similara cu diferenta ca vecinii unui nod adaugat in coada se cauta in lista corespunzatoare lui:

#include<conio.h>

#include<fstream.h>

struct nod

;

nod *L[20];

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

int m,n;

int prim,ultim,C[100];

void bfi_lis()

//il marchez ca fiind vizitat

p=p->next;

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

}

void afisare(int nr_nod)

cout<<endl;}

void main()

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()

;//il marchez ca fiind vizitat

p=p->next;}

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

bfr_lis();

}

2. Parcurgerea in adancime (Depth First Search, DFS):

DFS poate fi imaginata mai usor sub forma recursiva. Alegem un nod sursa. Dupa ce il marcam ca vizitat, consideram pe rand fiecare dintre vecinii sai ca fiind sursa. Muchiile catre noduri deja vizitate (inclusiv nodul original) practic nu vor conta (desi trebuiesc testate). In desenele de mai jos incerc sa simulez perspectiva nodului din pasul curent (observati cum acesta nu are acces la nodurile incetosate din cauza vecinilor deja vizitati):

Semnificatia culorilor ramane aceeasi ca la BFS:

alb daca nodul nu a fost vizitat;

gri daca nodul a fost vizitat dar nu i-am parcurs toti vecinii;

negru daca am parcurs toti vecinii nodului.

Vom mai introduce doua variabile care se vor dovedi utile in unele aplicatii:

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

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

Algoritmul:

Punand cap la cap informatiile de pana acum obtinem urmatorul algoritm:

// = = = = = = initializari = = = = = = ==

pentru fiecare nod u al grafului

timp = 0;

// = pentru a ne asigura ca se parcurg toate componentele conexe =

pentru fiecare nod al grafului

daca (culoare[nod] == alb)

PARCURGE(u);

// = = = = = = == va parcurge o componenta conexa = = =

PARCURGE(u)

}

culoare[u] = negru;

tFin[u] = ++timp;

Obs: Algoritmul este facut pentru a acoperi toate nodurile, chiar daca graful are mai multe componente conexe. Metoda PARCURGE corespunde acoperirii unei componente conexe.

Obs: Ganditi-va la asemanarile cu BKT. Daca am avea un arbore in care fiecare nod ar reprezenta asocierea unei variabile cu o valoare si de la fiecare nod s-ar porni catre toate atribuirile posibile ale urmatoarei variabile parca seamana, nu? Mai mult decat atat, si la DFS, ca si la BKT, ne putem intreba in ce ordine sa luam vecinii ca sa ajungem mai repede intr-un nod anume

Obs.: Si la DFS, ca si la BFS, in urma parcurgerii se obtin arbori. Acestia se numesc arbori de adancime. Spre exemplu:

Evident, pe acest arbore s-ar putea adauga si muchiile pe care nu le-am folosit in parcurgere, dar l-ar face sa nu mai fie arbore. Totusi, in cazul grafurilor orientate, si aceste muchii au o semnificatie speciala.

Am transformat graful din exemplul precedent intr-unul orientat si i-am mai adaugat cateva noduri. Si de data asta i-am figurat toate muchiile. Acestea vor fi:

muchii inainte: muchia (1,4);

muchii inapoi: muchia (3,1);

muchii de traversare: muchia (9,1).

Un alt exemplu pentru grafuri neorientate

Se porneste de la un nod oarecare x.

Se alege primul vecin al lui x care nu a fost inca vizitat.

Pentru nodul ales se reia procedeul.

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

Structuri de date necesare implementarii:

Matrice de adiacenta (sau alte variante): a

Stiva: s (in care se memoreaza nodurile in ordinea parcurgerii)

Daca se implementeaza varianta recursiva se va folosi stiva procesorului

Vectorul nodurilor vizitate: v

int a[20][20],u;

int v[20];

void DF(int x)

Pentru grafuri orientate

x = 10

Parcurgerea este similara, punandu-se conditia de parcurgere a tuturor vecinilor unui nod indiferent de sens.

Aplicatii ale metodelor de parcurgere

//parcurgerea unui graf in adancime pentru determinarea ciclurilor care contin un nod specificat

#include <stdio.h>

#include <conio.h>

#define n 6

int m[n][n]=,

,

,

,

,

};

int s[n];

int varf=0;

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

void afisare()

void main()

} while (nod>n-1);

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

rand=nod; col=0;

parcurs=0;

while (parcurs==0)

else

}

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

}

}