DFS — Algorithme de parcours en profondeur expliqué

Le parcours en profondeur, ou DFS, est un algorithme qui permet d’explorer un arbre ou un graphe en suivant un chemin aussi loin que possible avant de revenir en arrière. En termes simples : le DFS continue à descendre jusqu’à être bloqué, puis revient au dernier endroit où une autre branche était disponible.

S’il faut retenir une seule idée, retenez celle-ci : le DFS signifie « aller en profondeur, puis revenir en arrière ».

Ce que fait le parcours en profondeur

Le DFS peut être utilisé sur des arbres comme sur des graphes généraux. En partant d’un nœud, il se déplace de façon répétée vers un voisin non visité. Lorsqu’il atteint un nœud qui n’a plus de voisin non visité, il revient au nœud précédent et continue à partir de là.

Ce retour arrière est le comportement qui le définit. Dans les implémentations récursives, la pile d’appels s’en charge automatiquement. Dans les implémentations itératives, une pile explicite joue le même rôle.

Pourquoi l’ordre du DFS peut changer

Le DFS ne produit pas un ordre de visite universel. L’ordre exact dépend de l’ordre dans lequel les voisins sont examinés.

Par exemple, si un nœud a pour voisins $B$ et $C$, visiter $B$ en premier peut donner un ordre DFS différent de celui obtenu en visitant $C$ d’abord. Dans les deux cas, il s’agit bien d’un DFS, car la règle reste la même : aller le plus loin possible avant d’explorer une branche sœur.

Exemple de DFS sur un petit graphe

Supposons que le graphe ait les connexions suivantes :

• $A$ est connecté à $B$ et $C$
• $B$ est connecté à $D$ et $E$
• $C$ est connecté à $F$

Supposons que nous examinions toujours les voisins de gauche à droite et que nous commencions à $A$.

Le DFS se déroule ainsi :

1. Visiter $A$
2. Aller à $B$
3. Aller à $D$
4. $D$ n’a pas de voisin non visité, donc revenir à $B$
5. Depuis $B$, aller à $E$
6. $E$ est terminé, donc revenir à $B$, puis à $A$
7. Depuis $A$, aller à $C$
8. Depuis $C$, aller à $F$

Un ordre de visite DFS valide est donc :

$$A, B, D, E, C, F$$

L’idée essentielle est que le DFS termine le côté $A \to B$ avant de commencer le côté $A \to C$. Si vous changiez l’ordre des voisins, l’ordre de visite pourrait aussi changer.

Pourquoi le retour arrière utilise une pile

Le DFS a toujours besoin d’un moyen de se souvenir de l’endroit où revenir après avoir atteint une impasse. C’est pourquoi les piles apparaissent naturellement dans le DFS.

Dans un DFS récursif, chaque appel de fonction attend pendant que la recherche va plus en profondeur, puis le programme revient dans l’ordre inverse lors du retour arrière. Dans un DFS itératif, on empile des nœuds dans une pile puis on les dépile lorsqu’il est temps de reprendre depuis le point inachevé le plus récent.

Complexité en temps et en espace du DFS

Si le graphe est stocké sous forme de liste d’adjacence et que chaque sommet est marqué lors de sa première visite, le DFS s’exécute en

$$O(V + E)$$

temps pour la partie atteignable du graphe, où $V$ est le nombre de sommets et $E$ le nombre d’arêtes.

L’espace supplémentaire est généralement de

$$O(V)$$

car la structure des sommets visités et la pile de récursion ou la pile explicite peuvent chacune croître avec le nombre de sommets.

Erreurs fréquentes avec le DFS

Oublier de marquer les nœuds visités

Dans un graphe général, oublier la vérification des nœuds visités peut faire tourner le DFS indéfiniment dans un cycle. Même dans un arbre stocké comme un graphe non orienté, il faut quand même éviter de revenir immédiatement au parent, sauf si votre code gère explicitement ce cas.

Supposer que le DFS trouve le plus court chemin

Le DFS peut trouver un chemin, mais il ne garantit généralement pas un plus court chemin dans un graphe non pondéré. Si l’objectif est de trouver le plus court chemin et que toutes les arêtes ont le même poids, le BFS est généralement le bon point de départ.

Considérer l’ordre du DFS comme unique

L’ordre dépend de l’ordre des voisins. Si cet ordre change, l’ordre du parcours peut changer lui aussi.

Quand le parcours en profondeur est utilisé

Le DFS est utile lorsque vous voulez explorer une structure plutôt que simplement la distance la plus proche d’abord. Parmi ses usages courants :

• vérifier si un nœud est atteignable
• trouver les composantes connexes
• détecter des cycles dans certains contextes de graphes
• parcourir des arbres
• résoudre des problèmes de type retour arrière, comme des labyrinthes ou des recherches de puzzles

La raison principale pour laquelle il apparaît si souvent est que « aller en profondeur, puis revenir en arrière » correspond à de nombreuses structures de problèmes récursifs.

DFS vs BFS : la différence pratique

Le DFS descend d’abord le long d’une branche. Le BFS explore tous les nœuds à une distance donnée avant de passer à la distance suivante.

Si vous vous intéressez à une exploration exhaustive ou à une structure récursive, le DFS est souvent naturel. Si vous cherchez le plus court chemin dans un graphe non pondéré, le BFS est souvent le choix initial le plus sûr.

Essayez un parcours similaire

Dessinez un petit graphe à six nœuds et choisissez un ordre fixe pour les voisins. Exécutez le DFS à la main et notez exactement quand vous avancez et quand vous revenez en arrière. Si votre ordre change après avoir réordonné les voisins, ce n’est pas un bug. Cela fait partie du fonctionnement du DFS.