Parcurgerea grafurilor (DFS, BFS, algoritmul lui Dijkstra)

Parcurgerea grafurilor reprezintă un fundament al algoritmicii și al informaticii teoretice, fiind esențială pentru înțelegerea structurilor de date avansate și a algoritmilor pe grafuri. În cadrul liceului, la disciplinele de informatică (inclusiv pentru Bacalaureat), se studiază două metode principale de parcurgere: DFS (Depth-First Search) și BFS (Breadth-First Search), precum și algoritmul lui Dijkstra pentru determinarea drumurilor minime într-un graf ponderat cu costuri nenegative.

DFS (parcurgerea în adâncime) explorează graful mergând cât mai departe pe fiecare ramură, apoi revine (backtracking). Se implementează recursiv sau cu o stivă (stack). DFS este util pentru detectarea ciclurilor, sortarea topologică (în grafuri orientate aciclice), determinarea componentelor conexe și a arborilor de adâncime. Complexitatea sa este O(V + E), unde V = numărul de noduri, E = numărul de muchii.

BFS (parcurgerea în lățime) explorează graful pe niveluri, pornind de la un nod sursă și vizitând toți vecinii acestuia, apoi vecinii vecinilor etc. Se implementează cu o coadă (queue). BFS este ideal pentru găsirea celui mai scurt drum (în număr de muchii) într-un graf neponderat și pentru verificarea bipartitismului unui graf. Complexitatea sa este tot O(V + E).

Algoritmul lui Dijkstra generalizează BFS pentru grafuri ponderate cu muchii de costuri nenegative. El menține o mulțime de noduri nevizitate și actualizează distanțe minime estimative, alegând de fiecare dată nodul cu cea mai mică distanță curentă. Se implementează eficient cu un min-heap (priority queue).

Algoritmul lui Dijkstra este utilizat pe scară largă în rețele de calculatoare (routing) și în sisteme de navigație. Complexitatea implementării cu heap este O((V+E) log V).

Pentru Bacalaureat, elevii trebuie să cunoască implementarea în pseudocod (sau C++) a acestor algoritmi, să înțeleagă principiul de funcționare, să poată aplica manual pe exemple mici și să identifice complexitățile. De asemenea, este important să distingă cazurile de utilizare: DFS pentru probleme de backtracking sau cicluri, BFS pentru drumuri minime neponderate, Dijkstra pentru drumuri minime ponderate (costuri pozitive).

În această lecție, vom prezenta exemple concrete de aplicare și exerciții de tip grilă, răspuns liber și completare, pentru a fixa cunoștințele.

Exemple

• Exemplul 1 (DFS într-un graf neorientat): Fie graful G cu nodurile {1,2,3,4} și muchiile (1-2), (1-3), (2-4). Parcurgere DFS pornind din nodul 1: se vizitează 1, apoi se alege vecinul 2 (sau 3, depinde de ordinea în listă). Din 2, se merge la 4 (nevizitat). Apoi se revine la 1 și se vizitează 3. Ordinea de vizitare: 1,2,4,3. Se observă că drumul în adâncime formează un arbore DFS.
• Exemplul 2 (BFS într-un graf neorientat): Același graf. BFS din nodul 1: se introduce 1 în coadă, se vizitează și se marchează. Se extrag vecinii: 2 și 3 se introduc în coadă și se vizitează (nivel 1). Apoi se extrage 2, vecinii săi: 4 (nevizitat) se introduce și se vizitează (nivel 2). Apoi se extrage 3 (nu are vecini noi), apoi 4. Ordinea: 1,2,3,4. Distanța minimă de la 1 la 4 este 2 muchii.
• Exemplul 3 (Dijkstra pe un graf ponderat): Fie graful orientat cu nodurile {A,B,C,D} și muchiile: A->B (4), A->C (2), B->C (1), B->D (5), C->D (8). Pornind din A, inițial dist(A)=0, dist(B)=inf, dist(C)=inf, dist(D)=inf. Se introduce A în heap. Se extrage A, se actualizează dist(B)=4, dist(C)=2. Se extrage C (cel mai mic), se actualizează dist(D)=2+8=10. Apoi se extrage B (dist=4), se actualizează dist(D)=min(10, 4+5=9) => 9. Se extrage D (dist=9). Rezultat: drum minim A->D = 9 (A->B->D).

Concepte cheie: DFS (Depth-First Search) - parcurgere în adâncime cu stivă sau recursivitate, BFS (Breadth-First Search) - parcurgere în lățime cu coadă, Algoritmul lui Dijkstra - drum minim în grafuri ponderate cu costuri nenegative, folosind min-heap, Complexități: O(V+E) pentru DFS/BFS, O((V+E) log V) pentru Dijkstra, Aplicații: detectare cicluri, sortare topologică, drumuri minime, bipartitism