Motivation

Le DFS explore un graphe en s'engageant dans un chemin et en le suivant aussi loin que possible, puis en revenant sur ses pas jusqu'au dernier sommet ayant un voisin non exploré.

Pourquoi apprendre le DFS ?

• Fondamental : il est à la base de la détection de cycles, du tri topologique, des composantes connexes et de nombreux autres algorithmes.
• Simple et peu coûteux : il s'exécute en un temps O(V + E) en utilisant une pile (ou la récursion) et un marqueur de visite.
• Polyvalent : le même parcours permet de répondre à des questions telles que « ces deux sommets sont-ils connectés ? » et « combien de parties distinctes le graphe possède-t-il ? »

Pour que les résultats restent prévisibles, nous visitons toujours les voisins d'un sommet par ordre croissant.