Qu'est-ce que la recherche en profondeur (DFS)?

Question

Accepted Answer

**DFS** explore un graphe en allant aussi loin que possible le long de chaque branche avant de revenir en arrière. Elle utilise une **pile** (souvent la pile d'appels via la récursion) et visite un chemin complet avant d'explorer les alternatives.

## L'idée

À partir d'un nœud, on recurse dans un voisin non visité et on continue en profondeur ; quand on est bloqué, on remonte et on essaie une autre branche.

## Exemple

```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 |
|---|-----|-----|
| Structure | queue | stack / recursion |
| Trouve | plus court (non pondéré) | n'importe quel chemin |
| Mémoire | O(V) frontier | O(depth) |
| Bon pour | chemins les plus courts, niveaux | cycles, tri topologique, composantes |

## Complexité

- **Temps:** O(V + E). **Espace:** O(V) (profondeur de récursion + visité).

## Pièges

Les graphes profonds peuvent déborder la pile de récursion — utiliser une pile explicite. Suivre `visited` pour gérer les cycles.

## Pourquoi c'est important

DFS est à la base de la détection de cycles, du tri topologique, des composantes connexes et de la génération de labyrinthe/chemin.

Son élégance récursive rend le code d'arbre et de graphe concis.

Savoir quand la profondeur d'abord surpasse la largeur d'abord est une compétence fondamentale en algorithmes de graphe.

	BFS	DFS
Structure	queue	stack / recursion
Trouve	plus court (non pondéré)	n'importe quel chemin
Mémoire	O(V) frontier	O(depth)
Bon pour	chemins les plus courts, niveaux	cycles, tri topologique, composantes