Le parcours en profondeur
Le parcours en profondeur se décrit facilement de manière récursive. Si
le point de départ est le point d'arrivée, on a fini. Sinon, on note le
point de départ comme visité, et on appelle le parcours en profondeur
sur chacun des noeuds non visités accessibles depuis le point de départ.
On s'arrête dès qu'un de ces parcours est un succès.
Pour savoir quel est le chemin effectivement calculé, il faut marquer le
noeud que l'on visite (il est potentiellement dans le chemin). En revanche
si aucun de ses voisins ne mène à la sortie, il faut retirer cette marque,
car on sait alors que le noeud n'est pas sur le chemin de la sortie.
Voici un exemple de parcours en profondeur sur le
petit labyrinthe :
