Parcours en profondeur (depth-first search)

Répertoire GitHub correspondant à cet article : https://github.com/peportier/ia03-dfs

Structure LIFO

En utilisant pour (la structure qui contient les nœuds rencontrés mais dont les successeurs ne sont pas encore calculés, les nœuds gris) une structure de pile LIFO (Last In First Out), nous obtenons le programme de recherche en profondeur dans un graphe.

 

Nous utilisons un visiteur trivial :

 

Version récursive

La recherche en profondeur s'écrit plus naturellement sous une forme récursive. La pile d'exécution, cachée au programmeur, remplace la structure de pile y.

 

Le programme principal teste les deux versions de la recherche en profondeur sur notre exemple.

 

Nous obtenons le résultat attendu.

1:6
2:5
3:1
4:4
5:3
6:2