38. Depth First Search (DFS - Recherche en Profondeur)

Le DFS est un algorithme de parcours de graphe qui explore le plus loin possible le long de chaque branche avant de revenir en arrière (backtracking).

Concept : Aller en Profondeur

Imaginez naviguer dans un labyrinthe. Le DFS est comme descendre un chemin jusqu'à ce que vous atteigniez une impasse, puis revenir (backtracking) et essayer le chemin suivant disponible.

Le DFS utilise généralement une Stack (Pile) (ou la récursivité, qui utilise la pile d'appels) pour se souvenir des nœuds à visiter ensuite.

Étapes de l'Algorithme (Récursif)

1. Commencer à un nœud source S.
2. Marquer S comme visité.
3. Pour chaque voisin V de S :
   • Si V n'est pas visité, appeler récursivement DFS sur V.

Cas d'Utilisation

• Trouver des composants connectés.
• Détecter des cycles dans un graphe.
• Tri topologique.