Algorithme de parcours en profondeur
L'algorithme de parcours en profondeur (ou DFS: Depth First Search) permet le parcours récursif d'un graphe quelconque.
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 du au fait que, contrairement à l'algorithme de parcours en largeur, il explore en fait « à fond » les chemins un par uns: pour chaque sommet, il prend le premier sommet voisin jusqu'à ce qu'un sommet n'aie plus de voisins (ou que tout 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 pas encore marqués.
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 pas encore explorés.
Implémentation récursive
DFS (graphe G, sommet s):
{
Marquer(S);
debut
POUR CHAQUE élément sfils de Voisin(s) FAIRE
SI NonMarqué(sfils)
ALORS DFS(G,sfils);
FIN-SI
FIN-POUR
fin
}
Voisin(s) : renvoie la liste des sommets adjacents à s.
Marquer(Noeud ) : marque un noeud, de manière à ne pas le considérer plusieurs fois.
SousArbre(noeud u) : retourne le sous-arbre de racine u.
Exemple
Voyons concrètement le fonctionnement de cet algorithme sur le graphe suivant:
Image manquante
Graphes.dfs-bfs.exemple.png
Image:Graphes.dfs-bfs.exemple.png
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.