03 — Le parcours en profondeur (DFS)

Ce que tu vas apprendre

• Le principe du parcours en profondeur
• Les versions récursive et itérative (avec pile)
• La différence pratique avec BFS
• Les applications : composantes, chemins, base du tri topologique

Prérequis

• 02 — Le parcours en largeur (BFS)
• La pile (LIFO) de la série Structures de données

Le parcours en profondeur (DFS, Depth-First Search) est l'autre façon fondamentale d'explorer un graphe. Là où BFS avance par cercles concentriques, DFS plonge : il suit un chemin aussi loin que possible, puis revient en arrière (backtrack) quand il est bloqué, pour explorer une autre branche. Cette stratégie en fait l'outil de base pour détecter des cycles, trouver des composantes connexes et ordonner des dépendances.

Le principe

DFS choisit un voisin, y va, puis depuis ce voisin choisit un autre voisin, et continue de s'enfoncer. Quand un sommet n'a plus de voisin non visité, il revient au sommet précédent et essaie une autre direction. Cette mécanique de plongée puis retour est naturellement récursive.

pythondef dfs(graphe, depart, visites=None):
    if visites is None:
        visites = set()
    visites.add(depart)
    for voisin in graphe[depart]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)  # on plonge avant de continuer
    return visites

La récursion fait le backtracking pour nous : quand l'appel récursif sur un voisin se termine, on revient automatiquement au sommet courant et on passe au voisin suivant. C'est la pile d'appels du langage qui gère le retour en arrière.

La version itérative avec pile

La récursion utilise implicitement une pile (celle des appels, vue dans la série Complexité). On peut rendre cette pile explicite, ce qui évite le risque de débordement de pile sur les très grands graphes profonds.

typescriptfunction dfsIteratif(graphe: Map<string, string[]>, depart: string): string[] {
  const visites = new Set<string>();
  const pile = [depart];
  const ordre: string[] = [];
  while (pile.length > 0) {
    const sommet = pile.pop()!;          // dépiler : LIFO
    if (visites.has(sommet)) continue;
    visites.add(sommet);
    ordre.push(sommet);
    for (const voisin of graphe.get(sommet) ?? []) {
      if (!visites.has(voisin)) pile.push(voisin);
    }
  }
  return ordre;
}

La structure de données est la seule différence avec BFS : BFS utilise une file (FIFO), DFS utilise une pile (LIFO). Échange la file contre une pile, et le parcours par niveaux devient un parcours en profondeur. Cette symétrie est élégante et vaut la peine d'être retenue.

DFS ou BFS

Les deux parcourent tout le graphe en O(V + E). Le choix dépend de ce qu'on cherche.

Si tu cherches le plus court chemin en nombre d'arêtes, c'est BFS. Si tu veux explorer toutes les structures, détecter des cycles, ordonner des dépendances ou trouver des chemins (pas forcément les plus courts), c'est DFS.

Les applications

DFS est la base de nombreux algorithmes :

• Composantes connexes : lancer un DFS depuis chaque sommet non encore visité ; chaque lancement découvre une composante entière. On compte ainsi les îlots d'un graphe.
• Détection de cycle : si DFS rencontre un sommet déjà dans la branche en cours d'exploration, il y a un cycle. C'est le sujet de l'article suivant.
• Tri topologique : l'ordre dans lequel DFS finit de traiter les sommets donne, inversé, un ordre topologique valide (article 05).
• Recherche de chemin et backtracking : résolution de labyrinthes, de sudokus, exploration de toutes les combinaisons. Le backtracking, technique centrale, est un DFS sur l'arbre des possibilités.

pythondef composantes_connexes(graphe):
    visites = set()
    nb = 0
    for sommet in graphe:
        if sommet not in visites:
            dfs(graphe, sommet, visites)  # découvre une composante entière
            nb += 1
    return nb

Une note pratique : la version récursive est concise et lisible, mais sur un graphe très profond (des dizaines de milliers de sommets en ligne), elle peut dépasser la limite de pile du langage et lever une erreur. Sur de tels graphes, la version itérative avec pile explicite est plus sûre. C'est le compromis vu dans la série Complexité sur le coût mémoire de la récursion.

L'article suivant utilise DFS pour une tâche précise et fréquente : détecter les cycles, et reconnaître les graphes acycliques orientés (DAG).

Sources

• Tarjan, R. E. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2). (Article fondateur des applications du DFS)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 22.3 "Depth-First Search". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 4.1-4.2. Addison-Wesley.