Comme pour le parcours en largeur, on va utiliser l'exemple d'un site web modélisé par un graphe dans lequel les sommets représentent les pages et les arêtes représentent les liens hypertextes permettant d'aller d'une page à une autre.
On suppose que ce graphe est connexe, c'est-à-dire qu'à partir d'une page donnée, toute autre page est accessible par une série de liens (une chaîne).
On cherche à tester toutes les pages de ce site, c'est-à-dire à parcourir ce graphe en passant par tous ses sommets.
On va procéder à un parcours en profondeur du graphe en mettant les sommets successifs dans une pile (structure LIFO).
Voici la description intuitive de l'algorithme :
- On empile le sommet de départ (on visite la page d'accueil du site).
-
- Si le sommet de la pile possède des voisins qui ne sont pas dans la pile, ni déjà passés dans la pile, alors on sélectionne l'un de ces voisins et on l'empile (en le marquant de son numéro de découverte)
- Sinon on dépile (c'est-à-dire on supprime l'élément au sommet de la pile).
- On recommence au point 2 tant que la pile n'est pas vide.
En d'autres termes, on traite toujours en priorité les liens des pages les plus tard découvertes.
