Algorithme de parcours en profondeur

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.

Pour les graphes non orientés, il correspond à la méthode intuitive qu'on utilise pour trouver la sortie d'un labyrinthe sans tourner en rond.

Principe

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 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'est 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épile un sommet et on empile ses voisins non encore explorés.

Implémentation récursive

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

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

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

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 (en) effectue un double parcours en profondeur pour calculer les composantes fortement connexes d'un graphe orienté quelconque.

Voir aussi

• Algorithme de parcours en largeur
• Arbre de Galton-Watson
• Arbre enraciné

• Portail de l’algorithmique