Pe scurt
Parcurgerea grafurilor este o operație fundamentală care permite vizitarea tuturor nodurilor într-o ordine specifică, folosind fie metoda DFS (adâncime) cu stivă, fie BFS (lățime) cu coadă. Ambele metode au complexitatea O(n + m) și sunt esențiale pentru rezolvarea problemelor de la Bacalaureat și olimpiade.
Algoritmul DFS (Depth-First Search)
DFS explorează cât mai adânc posibil pe o ramură, apoi se întoarce prin backtracking, folosind o stivă (implicit prin recursivitate sau explicit cu o structură de stivă).
- Pentru a evita ciclurile, se marchează nodurile vizitate
- Se recomandă atenție la adâncimea stivei recursive (risc de stack overflow pentru grafuri mari)
- Complexitate: O(n + m) în cazul reprezentării cu liste de adiacență
Aplicații practice ale DFS:
- Detectarea ciclurilor – dacă întâlnim un nod deja vizitat care nu este părintele curent, avem ciclu (muchii de întoarcere)
- Sortarea topologică – prin postordine
- Găsirea componentelor conexe
- Detectarea punților/punctelor de articulație
Exemplu DFS – Graf neorientat cu 5 noduri:
- Muchii: 1-2, 1-3, 2-4, 3-4, 4-5
- Parcurgere din nodul 1: se vizitează 1, apoi 2 (vecin), apoi 4, apoi 5, apoi se întoarce la 4, apoi 3 (prin muchia 1-3)
- Ordinea: 1, 2, 4, 5, 3
Exemplu DFS – Graf orientat cu 4 noduri:
- Muchii: 1->2, 1->3, 2->4, 3->4
- Parcurgere recursivă din 1: intră în 1, marchează, apoi recursiv în 2, marchează, apoi în 4, marchează; întoarcere la 2, apoi la 1; apoi în 3, marchează, apoi în 4 (deja vizitat)
- Ordinea: 1, 2, 4, 3
- Observație: DFS nu dă neapărat drumul minim
Exemplu DFS – Graf neorientat cu ciclu (triunghi):
- Noduri: 1-2-3-1
- DFS din 1: 1, 2, 3 (prin muchia 2-3), se întoarce la 2, apoi la 1 (muchia 1-3 deja vizitată)
- Pentru detectarea ciclurilor, DFS este metoda preferată
Algoritmul BFS (Breadth-First Search)
BFS explorează nivel cu nivel, folosind o coadă, asigurând astfel găsirea celui mai scurt drum (în număr de muchii) într-un graf neponderat.
- Se extrag nodurile în ordinea descoperirii
- Complexitate: O(n + m) în cazul reprezentării cu liste de adiacență
Aplicații practice ale BFS:
- Shortest path în grafuri neponderate
- Parcurgerea nivelurilor (de exemplu, în algoritmi de căutare)
- Bipartitia unui graf
Exemplu BFS – Graf neorientat cu 5 noduri:
- Muchii: 1-2, 1-3, 2-4, 3-4, 4-5
- BFS din 1: coada: 1, apoi extrag 1 și adaug 2 și 3; extrag 2 și adaug 4; extrag 3 și adaug (4 deja vizitat); extrag 4 și adaug 5
- Ordinea: 1, 2, 3, 4, 5
Exemplu BFS – Graf orientat cu 4 noduri:
- Muchii: 1->2, 1->3, 2->4, 3->4
- BFS din 1: coada: 1; extrag 1, adaug 2,3; extrag 2, adaug 4; extrag 3, adaug 4 (deja)
- Ordinea: 1, 2, 3, 4
- Observație: BFS dă distanța minimă (1->4 în 2 pași prin 2 sau 3)
Exemplu BFS – Graf neorientat cu ciclu (triunghi):
- Noduri: 1-2-3-1
- BFS: 1, 2, 3
- Detectarea ciclurilor prin BFS este mai puțin directă decât prin DFS
Aspecte cheie pentru implementare
- Gestionarea corectă a stării nodurilor: nevizitat, în curs de explorare, vizitat
- Evitarea blocajelor
- La Bacalaureat, se cer implementări în pseudocod sau C/C++ pentru grafuri orientate/neorientate
- Reprezentarea poate fi prin matrice de adiacență sau liste de adiacență
- În grafuri orientate, atât DFS cât și BFS pot fi aplicate similar, dar cu atenție la direcția muchiilor
- Pentru grafuri cu costuri, BFS se aplică doar pe muchii unitate
Verifică-te!
- Care este diferența fundamentală între structura de date folosită de DFS (stivă) și cea folosită de BFS (coadă) și cum influențează aceasta ordinea de parcurgere?
- În ce situație specifică BFS este preferat față de DFS și de ce?
- Cum poate fi detectat un ciclu într-un graf neorientat folosind DFS și ce reprezintă o muchie de întoarcere (back edge)?