Parcours en profondeur
Période historique : 1882
Depth-First Search (DFS) : exploration plongeant le plus loin possible le long de chaque branche via une pile LIFO.
Contenu & Formulation mathématique
Genèse & Portée historique
Algorithme récursif s'enfonçant au cœur du graphe jusqu'à une impasse avant de rebrousser chemin (backtracking). Fondé sur une pile, il s'exécute en O(V + E) et sert de colonne vertébrale au tri topologique, à la détection de cycles et aux algorithmes de Tarjan et Kosaraju.
Charles Pierre Trémaux a décrit au XIXe siècle la première version du parcours en profondeur comme méthode systématique pour sortir de n'importe quel labyrinthe sans jamais tourner en rond.
Filiations & Relations conceptuelles (1)
Objet de collection MathTCG
Parcours en profondeur
Principe : Depth-First Search (DFS) : exploration plongeant le plus loin possible le long de chaque branche via une pile LIFO.
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.