Parcours en profondeur (DFS)

Entrez dans un labyrinthe, avancez jusqu'à une impasse, puis revenez au dernier embranchement et essayez le chemin suivant. Le parcours en profondeur explore un graphe de la même façon. C'est l'un des algorithmes de graphe les plus simples, et la pile qu'il tient en dit plus long qu'on ne le croirait.

Un graphe où une longue chaîne de nœuds depuis le départ est surlignée en jaune, les nœuds terminés en violet clair, et la pile dessinée dessous comme une rangée de carrés
Un graphe où une longue chaîne de nœuds depuis le départ est surlignée en jaune, les nœuds terminés en violet clair, et la pile dessinée dessous comme une rangée de carrés

L'idée

Un graphe est un ensemble de nœuds reliés par des arêtes : des pièces et des portes, des pages web et des liens, des tâches et les tâches dont elles dépendent. Le parcours en profondeur visite chaque nœud qu'il peut atteindre depuis un départ, mais dans un ordre particulier : il repart toujours du nœud atteint le plus récemment. Il tient une pile des nœuds dans lesquels il se trouve. Un nouveau nœud va au sommet, et un nœud n'en sort que lorsque tout ce qui l'entoure a été exploré.

Pas à pas

Placez le départ dans la pile et donnez-lui le numéro de visite 1. Regardez le voisin suivant du nœud au sommet. S'il n'a pas encore été vu, donnez-lui le numéro de visite suivant, retenez le nœud depuis lequel il a été atteint, et placez-le au sommet de la pile. S'il a déjà été vu, ignorez-le. Quand le nœud au sommet n'a plus de voisins à examiner, il est terminé : retirez-le et continuez avec le nœud en dessous. Arrêtez-vous quand la pile est vide, ou quand la cible est atteinte.

Un exemple

Prenez un graphe avec les arêtes A–B, A–C, B–D, C–D, C–E et D–F, partez de A, et examinez les voisins dans l'ordre alphabétique. De A, le parcours va à B, de B à D, de D à C, et de C à E, donc la pile est A, B, D, C, E. En chemin, C voit A, qui est encore dans la pile : l'arête C–A ferme le cycle A, B, D, C. E n'a rien de nouveau, il est donc terminé, puis C, et le parcours revient à D, qui a encore F. L'ordre de visite est A, B, D, C, E, F. Avec E comme cible, le DFS s'arrête avec le chemin A → B → D → C → E, soit quatre arêtes, alors que A → C → E n'en prend que deux.

À quoi il sert

La pile est toujours un chemin du départ jusqu'au nœud courant, ce qui rend le DFS naturel pour les labyrinthes et les casse-têtes : c'est l'idée du backtracking (retour sur trace). Dans un graphe non orienté, une arête vers un nœud encore dans la pile ferme un cycle. Dans un graphe orienté, lister les nœuds dans l'ordre inverse de celui où ils sont terminés donne un ordre topologique, où chaque tâche vient après celles dont elle dépend. Le parcours en profondeur trouve aussi les composantes connexes, les ponts et les points d'articulation, et sa version aléatoire est une façon classique de générer des labyrinthes.

Histoire

Au XIXe siècle, le mathématicien français Charles Pierre Trémaux a décrit une méthode pour sortir de n'importe quel labyrinthe en marquant les couloirs : c'est un parcours en profondeur fait à la craie. En 1972 et 1973, Robert Tarjan et John Hopcroft ont montré que le DFS résout de nombreux problèmes de graphes en temps linéaire, des composantes fortement connexes au test qui dit si un graphe peut être dessiné sans croisements. Ils ont reçu le prix Turing 1986 en partie pour ces travaux.

Robert Tarjan, qui avec John Hopcroft montra en 1972–73 que la recherche en profondeur résout de nombreux problèmes de graphes en temps linéaire ; ils reçurent le prix Turing 1986 en partie pour ce travail.
Robert Tarjan, qui avec John Hopcroft montra en 1972–73 que la recherche en profondeur résout de nombreux problèmes de graphes en temps linéaire ; ils reçurent le prix Turing 1986 en partie pour ce travail.

À vous d'explorer

Ouvrez l'application et appuyez sur Étape. Le nœud dont on examine les voisins est mis en évidence, les nœuds dans la pile sont en bleu et les nœuds terminés en vert, chacun avec son numéro de visite. La pile est affichée sous le graphe, du départ au nœud au sommet. Surveillez la ligne d'état pour repérer les arêtes qui ferment un cycle, et choisissez une cible pour voir combien le chemin trouvé peut être long comparé au parcours en largeur.

Questions fréquemment posées

Quelle est la complexité en temps du DFS ?

O(V + E) pour V nœuds (vertices en anglais) et E arêtes (edges) : chaque nœud entre et sort de la pile une fois, et chaque arête est examinée depuis ses deux extrémités. Il faut O(V) de mémoire en plus pour la pile et les marques.

Pourquoi le DFS utilise-t-il une pile ?

Parce que la règle dernier entré, premier sorti fait repartir le parcours du nœud le plus récent, puis revenir à celui d'avant. La récursivité fait la même chose avec la pile d'appels du programme. Avec une file à la place, le parcours s'étendrait anneau par anneau : c'est le parcours en largeur.

Le DFS récursif pose-t-il problème sur de grands graphes ?

Cela peut arriver : un long chemin signifie une récursion profonde, et beaucoup de langages limitent la profondeur des appels. Une pile explicite dans une boucle évite cette limite tout en visitant les nœuds dans le même ordre.

Où utilise-t-on le DFS ?

Pour résoudre des labyrinthes et des casse-têtes par backtracking, trouver des cycles, ordonner des tâches selon leurs dépendances (tri topologique), trouver les composantes connexes et fortement connexes, générer des labyrinthes, et dans les compilateurs et les outils de build qui parcourent des graphes de dépendances.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer le parcours en profondeur