Algorithme de parcours en profondeur

L'algorithme de parcours en profondeur (ou parcours en profondeur, ou DFS, pour Depth-First Search) est un algorithme de parcours d'arbre, et plus généralement de parcours de graphe. Il se décrit naturellement de manière récursive. Son application la plus simple consiste à déterminer s'il existe un chemin d'un sommet à un autre.

Histoire

Pour les graphes non orientés, le parcours en profondeur correspond à la méthode intuitive qu'on utilise pour trouver la sortie d'un labyrinthe sans tourner en rond. Des algorithmes de parcours en profondeur sont formulés dès le XIX^e siècle. Édouard Lucas (1891) dans ses Récréations mathématiques en propose une solution rigoureuse^[1] dont il attribue l'idée à Charles Pierre Trémaux^[2]. Gaston Tarry en donne une autre solution^[3].

Principe

Exploration d'un labyrinthe à la manière du parcours en profondeur.

L'exploration d'un parcours en profondeur depuis un sommet S fonctionne comme suit. Il poursuit alors un chemin dans le graphe jusqu'à un cul-de-sac ou alors jusqu'à atteindre un sommet déjà visité. Il revient alors sur le dernier sommet où on pouvait suivre un autre chemin puis explore un autre chemin (voir vidéo ci-contre). L'exploration s'arrête quand tous les sommets depuis S ont été visités. Bref, l'exploration progresse à partir d'un sommet S en s'appelant récursivement pour chaque sommet voisin de S.

Le nom d'algorithme en profondeur est dû au fait que, contrairement à l'algorithme de parcours en largeur, il explore en fait « à fond » les chemins un par un : pour chaque sommet, il marque le sommet actuel, et il prend le premier sommet voisin jusqu'à ce qu'un sommet n'ait plus de voisins (ou que tous ses voisins soient marqués), et revient alors au sommet père.

Si G n'était pas un arbre, l'algorithme pourrait a priori tourner indéfiniment si on continuait l'exploration depuis un sommet déjà visité. Pour éviter cela, on marque les sommets que l'on visite, de façon à ne pas les explorer à nouveau.

Dans le cas d'un arbre, le parcours en profondeur est utilisé pour caractériser l'arbre.

Implémentation récursive

Durant l'exploration, on marque les sommets afin d'éviter de re-parcourir des sommets parcourus. Initialement, aucun sommet n'est marqué^[4].

explorer(graphe G, sommet s)
      marquer le sommet s
      afficher(s)
      pour tout sommet t voisin du sommet s
            si t n'est pas marqué alors
                   explorer(G, t);

Le parcours en profondeur d'un graphe G est alors :

parcoursProfondeurRec(graphe G)
      pour tout sommet s du graphe G
            si s n'est pas marqué alors
                   explorer(G, s)

Implémentation itérative

Il est possible d'implémenter le parcours en profondeur itérativement à l'aide d'une pile LIFO contenant les sommets à explorer : on désempile un sommet et on empile ses voisins encore non explorés.

parcoursProfondeurIter(graphe G, sommet s)
      p=creer_pile()
      p.empiler(s)
      tant que p est non vide
         s=p.depiler()
         si s n'est pas marqué
            marquer le sommet s
            afficher le sommet s
            pour tout sommet t voisin du sommet s
               si t n'est pas marqué
                   p.empiler(t)

Exemple

Voyons concrètement le fonctionnement du parcours en profondeur depuis le sommet A dans le graphe suivant :

Nous conviendrons que les sommets à gauche sur ce graphe seront choisis avant ceux de droite. Si l'algorithme utilise effectivement un marquage des sommets pour éviter de tourner indéfiniment en boucle, on aura alors l'ordre de visite suivant : A, B, D, F, E, C, G.

Supposons maintenant que nous n'utilisions pas la méthode de marquage, on aurait alors la visite des sommets suivants dans l'ordre: A, B, D, F, E, A, B, D, F, E, etc indéfiniment, puisque l'algorithme ne peut sortir de la boucle A, B, D, F, E et n'atteindra donc jamais C ou G.

Applications

Comme les autres algorithmes de parcours de graphe, l'algorithme de parcours en profondeur trouve l'ensemble des sommets accessibles depuis un sommet donné s, c'est-à-dire ceux vers lesquels il existe un chemin partant de s. Il s'agit précisément des sommets marqués par l'algorithme. Ceci s'applique à un graphe orienté ou non orienté. Sur un graphe non orienté, on peut utiliser cette propriété pour le calcul des composantes connexes.

Dans le cas d'un graphe orienté acyclique, le parcours en profondeur permet de calculer un tri topologique des sommets.

L'algorithme de Kosaraju effectue un double parcours en profondeur pour calculer les composantes fortement connexes d'un graphe orienté quelconque.

Complexité

La complexité du parcours est $O(|S|+|A|)$ où $|S|$ est le nombre de sommets et $|A|$ le nombre d'arcs^[4]. En 1985, John Reif a défini un problème de décision associé au parcours en profondeur et a montré qu'il est P-complet^[5]. Ce problème décision est le suivant : étant donné un graphe G et deux sommets u et v, décider si u apparait avant v dans le parcours en profondeur qui explore les sommets par ordre lexicographique. Cela signifie que le parcours en profondeur est difficile à paralléliser^[6]. Toutefois, le parcours en profondeur (mais pas avec un ordre lexicographique) est parallélisable sur une machine probabiliste et est dans la classe RNC^[7]. En 1997, Karger et al. énonce que le problème de savoir si le parcours est parallélisable sur un machine déterministe est ouvert^[8].

Notes et références

↑ Édouard Lucas, Récréations mathématiques (2^e éd.), A. Blanchard (Paris), 1891, pp. 47--55, [1]. Accès direct à la page : [2].
↑ « Parmi les diverses solutions de ce curieux problème de la Géométrie de situation, dont nous venons de donner l'énoncé, nous choisirons, comme la plus simple et la plus élégante, celle qui nous a été gracieusement communiquée par M. Trémaux, ancien élève de l'École Polytechnique, ingénieur des télégraphes; mais nous en avons modifié légèrement la démonstration. » in Récréations mathématiques, page 47.
↑ Gaston Tarry, « Le problème des labyrinthes », Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale, Sér. 3, 14, 1895, p. 187-190 [3] « Copie archivée » (version du 9 février 2015 sur Internet Archive).
↑ ^{a et b} (en) S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms
↑ John H. Reif, « Depth-first search is inherently sequential », Information Processing Letters, vol. 20, n^o 5,‎ 1985 (DOI 10.1016/0020-0190(85)90024-9)
↑ Kurt Mehlhorn et Peter Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer, 2008 (lire en ligne)
↑ (en) A. Aggarwal et R. J. Anderson, « A random 1-011-011-01algorithm for depth first search », Combinatorica, vol. 8, n^o 1,‎ 1^er mars 1988, p. 1–12 (ISSN 1439-6912, DOI 10.1007/BF02122548, lire en ligne, consulté le 27 septembre 2019)
↑ D. Karger et R. Motwani, « An $\NC$ Algorithm for Minimum Cuts », SIAM Journal on Computing, vol. 26, n^o 1,‎ 1^er février 1997, p. 255–272 (ISSN 0097-5397, DOI 10.1137/S0097539794273083, lire en ligne, consulté le 27 septembre 2019)

Voir aussi

Portail de l'informatique théorique

[1] Édouard Lucas, Récréations mathématiques (2^e éd.), A. Blanchard (Paris), 1891, pp. 47--55, [1]. Accès direct à la page : [2].

[2] « Parmi les diverses solutions de ce curieux problème de la Géométrie de situation, dont nous venons de donner l'énoncé, nous choisirons, comme la plus simple et la plus élégante, celle qui nous a été gracieusement communiquée par M. Trémaux, ancien élève de l'École Polytechnique, ingénieur des télégraphes; mais nous en avons modifié légèrement la démonstration. » in Récréations mathématiques, page 47.

[3] Gaston Tarry, « Le problème des labyrinthes », Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale, Sér. 3, 14, 1895, p. 187-190 [3] « Copie archivée » (version du 9 février 2015 sur Internet Archive).

[:1-4] {a et b} (en) S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms

[5] John H. Reif, « Depth-first search is inherently sequential », Information Processing Letters, vol. 20, n^o 5,‎ 1985 (DOI 10.1016/0020-0190(85)90024-9)

[mehlhorn-6] Kurt Mehlhorn et Peter Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer, 2008 (lire en ligne)

[7] (en) A. Aggarwal et R. J. Anderson, « A random 1-011-011-01algorithm for depth first search », Combinatorica, vol. 8, n^o 1,‎ 1^er mars 1988, p. 1–12 (ISSN 1439-6912, DOI 10.1007/BF02122548, lire en ligne, consulté le 27 septembre 2019)

[8] D. Karger et R. Motwani, « An $\NC$ Algorithm for Minimum Cuts », SIAM Journal on Computing, vol. 26, n^o 1,‎ 1^er février 1997, p. 255–272 (ISSN 0097-5397, DOI 10.1137/S0097539794273083, lire en ligne, consulté le 27 septembre 2019)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]