Structure des données - Première traversée en profondeur
L'algorithme de recherche en profondeur (DFS) parcourt un graphique dans un mouvement vers la profondeur et utilise une pile pour se souvenir d'obtenir le sommet suivant pour démarrer une recherche, lorsqu'une impasse se produit dans une itération.
Comme dans l'exemple donné ci-dessus, l'algorithme DFS parcourt de S à A à D à G à E à B d'abord, puis à F et enfin à C. Il utilise les règles suivantes.
Rule 1- Visitez le sommet non visité adjacent. Marquez-le comme visité. Affichez-le. Poussez-le dans une pile.
Rule 2- Si aucun sommet adjacent n'est trouvé, affiche un sommet de la pile. (Il fera apparaître tous les sommets de la pile, qui n'ont pas de sommets adjacents.)
Rule 3 - Répétez la règle 1 et la règle 2 jusqu'à ce que la pile soit vide.
| Étape | Traversée | La description |
|---|---|---|
| 1 |  |
Initialisez la pile. |
| 2 |  |
marque Scomme visité et mettez-le sur la pile. Explorez n'importe quel nœud adjacent non visité depuisS. Nous avons trois nœuds et nous pouvons choisir l'un d'entre eux. Pour cet exemple, nous prendrons le nœud dans un ordre alphabétique. |
| 3 |  |
marque Acomme visité et mettez-le sur la pile. Explorez tout nœud adjacent non visité de A. Les deuxS et D sont adjacents à A mais nous nous préoccupons uniquement des nœuds non visités. |
| 4 |  |
Visite Det marquez-le comme visité et mettez-le sur la pile. Ici nous avonsB et C nœuds, qui sont adjacents à Det les deux ne sont pas visités. Cependant, nous choisirons à nouveau par ordre alphabétique. |
| 5 |  |
Nous choisissons B, marquez-le comme visité et mettez-le sur la pile. IciBn'a aucun nœud adjacent non visité. Alors, on popB de la pile. |
| 6 |  |
Nous vérifions le haut de la pile pour revenir au nœud précédent et vérifions s'il contient des nœuds non visités. Ici, on trouveD être au sommet de la pile. |
| sept |  |
Seul le nœud adjacent non visité provient de D est Cmaintenant. Alors on visiteC, marquez-le comme visité et placez-le sur la pile. |
Comme Cn'a pas de nœud adjacent non visité, nous continuons donc à sauter la pile jusqu'à ce que nous trouvions un nœud qui a un nœud adjacent non visité. Dans ce cas, il n'y en a pas et nous continuons à sauter jusqu'à ce que la pile soit vide.
Pour connaître l'implémentation de cet algorithme en langage de programmation C, cliquez ici .