Informatică Algoritmi
Algoritmi de parcurgere grafuri BFS DFS
BFS (Breadth-First Search) și DFS (Depth-First Search) sunt algoritmi fundamentali pentru parcurgerea grafurilor, folosiți pentru a explora noduri și muchii. BFS parcurge graful pe niveluri, începând de la un nod sursă, folosind o coadă, iar DFS explorează cât mai adânc posibil pe fiecare ramură, folosind o stivă sau recursivitate. Ambii au complexitate O(V+E) pentru un graf cu V noduri și E muchii.
Pași pentru BFS
- 1 Inițializează Alege un nod de start, marchează-l vizitat, și adaugă-l într-o coadă.
- 2 Extrage din coadă Scoate primul nod din coadă, procesează-l, și adaugă toți vecinii nevizitați în coadă, marcându-i vizitați.
- 3 Repetă Continuă până când coada devine goală, asigurând parcurgerea pe niveluri.
Pași pentru DFS
- 1 Alege nodul de start Marchează nodul curent ca vizitat și începe explorarea.
- 2 Explorează recursiv Pentru fiecare vecin nevizitat, apelează DFS recursiv pe acel nod.
- 3 Revino După ce toți vecinii sunt explorați, revine la nodul anterior, permițând parcurgerea în adâncime.
Aplicații practice
- BFS pentru drumuri minime În grafuri neponderate, BFS găsește cel mai scurt drum de la sursă la toate nodurile, de exemplu în rețele sociale.
- DFS pentru detectarea ciclurilor DFS poate identifica cicluri în grafuri prin marcarea nodurilor în curs de explorare, util în analiza dependențelor.
Folosește BFS pentru drumuri minime și DFS pentru explorare exhaustivă sau backtracking.