De ce contează?
Ești într-un labirint, cu o sfoară legată la intrare. Strategia ta e simplă: mergi pe primul coridor pe care nu l-ai mai bătut, cât poți de departe. Când ajungi într-o fundătură, te întorci la ultima răscruce și încerci alt coridor de acolo. Sfoara îți spune mereu pe unde să te întorci. Așa explorezi tot labirintul, fără să te rătăcești. DFS face exact asta pe un graf.
Intuiția
DFS (Depth-First Search, parcurgere în adâncime) pleacă dintr-un nod și intră cât de adânc poate pe un drum, vizitând mereu primul vecin nevizitat. Când nodul curent nu mai are vecini noi, se întoarce (backtrack) la nodul de unde a venit și continuă de acolo. Spre deosebire de BFS, care explorează nivel cu nivel, DFS se afundă pe un singur drum până se blochează, apoi dă înapoi.
Partea grea la explorare nu e mersul înainte, ci întoarcerea. La DFS,
întoarcerea e gratuită: când dfs(vecin) se termină, execuția revine automat în
dfs(nod), exact la vecinul următor. Stiva de apeluri e „sfoara" ta — nu ții tu
minte drumul înapoi, îl ține limbajul.