Algorithme de parcours en profondeur

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme de parcours en profondeur (ou DFS, pour Depth First Search) est un algorithme de parcours de graphe qui 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. Trémaux et Tarry ont, chacun de leur côté, formulé des algorithmes de parcours en profondeur dès le XIXe siècle.

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. É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[modifier | modifier le code]

C'est un algorithme de recherche qui 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 tourner indéfiniment, c'est pour cela que l'on doit en outre marquer chaque sommet déjà parcouru, et ne parcourir que les sommets non encore marqués.

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

Enfin, on notera qu'il est tout à fait possible de l'implémenter itérativement à l'aide d'une pile LIFO contenant les sommets à explorer : on désempile un sommet et on empile ses voisins non encore explorés.

Implémentation récursive[modifier | modifier le code]

Initialement, aucun sommet n'est marqué.

DFS (graphe G, sommet s)
{
  Marquer(s);
  POUR CHAQUE élément s_fils de Voisins(s) FAIRE
     SI NonMarqué(s_fils) ALORS
       DFS(G,s_fils);
     FIN-SI
  FIN-POUR
}

Voisins(s) : renvoie la liste des sommets adjacents à s.

Marquer(s) : marque un sommet s comme exploré, de manière à ne pas le considérer plusieurs fois.

Exemple[modifier | modifier le code]

Voyons concrètement le fonctionnement de cet algorithme sur le graphe suivant:

Graph.traversal.example.svg

L'algorithme DFS commence au sommet A, 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[modifier | modifier le code]

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 peut servir à 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.

Notes et références[modifier | modifier le code]

  1. Édouard Lucas, Récréations mathématiques (2e é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. Tarry, G. 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]

Voir aussi[modifier | modifier le code]