Algorithme de parcours en profondeur
Un article de Wikipédia, l'encyclopédie libre.
L'algorithme de parcours en profondeur (ou DFS, pour Depth First Search) permet le parcours récursif d'un graphe quelconque.
[modifier] 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 un: 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 non 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 non encore explorés.
[modifier] 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(Nœud ) : marque un nœud, de manière à ne pas le considérer plusieurs fois.
SousArbre(nœud u) : retourne le sous-arbre de racine u.
[modifier] 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, C, G, E.
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.
Ou encore:
Profondeur(G,s) Pour chaque u dans N faire vu[u] := faux rp(G,s) rp(G,u) vu[u] := vrai pour chaque arete dans (u,v) dans A faire si vu[v] := faux alors rp(G,v)
G=(N,A), N étant les sommets et A les arêtes d'un graphe et s un sommet de depart.
vu est un tableau de booléen vu[i] := vrai si et seulement si le sommet est accessible de s.