Co to jest wyszukiwanie w głąb (DFS)?

Question

Accepted Answer

**DFS** eksploruje graf, idąc tak głęboko, jak to możliwe, wzdłuż każdej gałęzi, zanim cofnie się. Używa **stosu** (często stosu wywołań za pośrednictwem rekurencji) i odwiedza pełną ścieżkę, zanim zbada alternatywy.

## Idea

Z węzła, rekurencyjnie przejdź do nieodwiedzonego sąsiada i idź głębiej; gdy się utkniesz, cofnij się i spróbuj innej gałęzi.

## Przykład

```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 vs DFS

| | BFS | DFS |
|---|-----|-----|
| Struktura | queue | stack / rekurencja |
| Znajduje | najkrótsza (nieważona) | dowolna ścieżka |
| Pamięć | O(V) granica | O(głębokość) |
| Dobre dla | najkrótsze ścieżki, poziomy | cykle, sort topo, komponenty |

## Złożoność

- **Czas:** O(V + E). **Przestrzeń:** O(V) (głębokość rekurencji + odwiedzone).

## Pułapki

Głębokie grafy mogą spowodować przepełnienie stosu rekurencji — użyj jawnego stosu. Śledź `visited` aby obsługiwać cykle.

## Dlaczego to ważne

DFS stanowi podstawę detektora cykli, sortowania topologicznego, komponenty połączonych i generowania labirynt/ścieżki.

Jego rekurencyjna elegancja sprawia, że kod drzewa i grafu jest zwięzły.

Wiedza o tym, kiedy wyszukiwanie w głąb przebije wyszukiwanie wszerz, jest podstawową biegłością w algorytmach grafowych.

	BFS	DFS
Struktura	queue	stack / rekurencja
Znajduje	najkrótsza (nieważona)	dowolna ścieżka
Pamięć	O(V) granica	O(głębokość)
Dobre dla	najkrótsze ścieżki, poziomy	cykle, sort topo, komponenty