Informatică Algoritmi
Algoritmi parcurgere grafuri DFS BFS
DFS (Depth-First Search) și BFS (Breadth-First Search) sunt doi algoritmi fundamentali pentru parcurgerea grafurilor. DFS explorează cât mai adânc pe o ramură înainte de a reveni, iar BFS explorează nivel cu nivel, începând de la un nod sursă.
Pași algoritmului DFS
- 1 Marcați nodul curent Vizitați nodul de start și marcați-l ca vizitat.
- 2 Explorați recursiv Pentru fiecare vecin nevizitat, aplicați DFS recursiv.
- 3 Reveniți După ce toți vecinii sunt explorați, reveniți la nodul anterior.
Pași algoritmului BFS
- 1 Folosiți o coadă Adăugați nodul de start într-o coadă și marcați-l ca vizitat.
- 2 Extrageți și explorați Extrageți primul nod din coadă, vizitați-l și adăugați vecinii nevizitați în coadă.
- 3 Repetați Continuați până când coada este goală.
Alege DFS pentru căutări în adâncime sau BFS pentru căutări în lățime, în funcție de problema specifică, cum ar fi găsirea drumurilor cele mai scurte.