Ce este căutarea în profunzime (DFS)?

Question

Accepted Answer

**DFS** explorează un graf mergând cât mai adânc posibil de-a lungul fiecărei ramuri înainte de a se întoarce. Folosește o **stivă** (adesea stiva apelurilor prin recursiune) și vizitează o cale completă înainte de a explora alternative.

## Ideea

Dintr-un nod, recursați într-un vecin nevizitat și continuați adânc; când rămâneți blocat, retrageți-vă și încercați o altă ramură.

## Exemplu

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS versus DFS

| | BFS | DFS |
|---|-----|-----|
| Structură | coadă | stivă / recursiune |
| Găsește | cea mai scurtă (neponderat) | orice cale |
| Memorie | O(V) frontieră | O(adâncime) |
| Bun pentru | cai mai scurte, niveluri | cicluri, sort topo, componente |

## Complexitate

- **Timp:** O(V + E). **Spațiu:** O(V) (adâncime recursiune + vizitat).

## Capcane

Grafurile profunde pot cauza depășirea stivei de recursiune — utilizați o stivă explicită. Urmăriți `visited` pentru a gestiona ciclurile.

## De ce este important

DFS este la baza detecției ciclurilor, sortării topologice, componentelor conectate și generării labirint/cale.

Eleganta sa recursivă face codul arborelui și grafului concis.

Știrea când profunzime-mai-întâi bate lățime-mai-întâi este o competență de bază în algoritmii grafului.

	BFS	DFS
Structură	coadă	stivă / recursiune
Găsește	cea mai scurtă (neponderat)	orice cale
Memorie	O(V) frontieră	O(adâncime)
Bun pentru	cai mai scurte, niveluri	cicluri, sort topo, componente