DFS (Depth-First Search)

Le concept du jour, c'est un algorithme classique : le DFS (Depth-First Search), ou parcours en profondeur. Imaginez un explorateur qui fonce tête baissée dans une grotte, toujours plus loin, jusqu'au bout du couloir avant même de penser à revenir. C'est exactement ça, le DFS. Choisir un chemin et le suivre aussi loin que possible, quitte à devoir faire demi-tour ensuite.

Le principe : l'exploration en profondeur

Contrairement à une exploration "en largeur" qui visiterait tous les voisins immédiats avant d'aller plus loin, le DFS s'engage à fond dans une direction. Il descend branche après branche, nœud après nœud, jusqu'à tomber sur un cul-de-sac ou un nœud déjà visité. C'est seulement à ce moment-là qu'il fait marche arrière pour explorer une autre voie.

Prenons un graphe simple :

A -- B -- D
|    |
C    E

Depuis A, le DFS pourrait visiter dans cet ordre : A → B → D (cul-de-sac, on revient) → E (cul-de-sac, on revient) → C. Toujours en profondeur, jamais en largeur.

Comment ça marche : la pile d'appels et le backtracking

Le DFS repose sur deux mécanismes fondamentaux.

La pile d'appels : à chaque fois qu'on visite un nœud, on "empile" le chemin parcouru. Cela permet de se souvenir d'où on vient. En pratique, la récursion gère cette pile automatiquement via la call stack du langage. C'est élégant, mais attention : sur un graphe très profond, cette pile peut déborder. C'est le fameux stack overflow.

Le backtracking : quand on atteint un cul-de-sac (plus de voisins à explorer, ou tous déjà visités), on remonte d'un niveau. On revient au dernier croisement pour tenter une autre voie. Ce "faire marche arrière" s'appelle le backtracking, et c'est la beauté du DFS : il explore tout, systématiquement, sans jamais se perdre.

Pour éviter de tourner en rond dans un graphe avec des cycles, on maintient un ensemble de nœuds déjà visités. Si on retombe sur un nœud déjà vu, on passe.

Implémentation TypeScript

La beauté du DFS, c'est qu'il s'écrit souvent en quelques lignes grâce à la récursivité. Voici une implémentation sur un graphe représenté par une liste d'adjacence.

// Représentation du graphe : chaque nœud pointe vers ses voisins
type Graph = Map<string, string[]>;
 
function dfs(
  graph: Graph,
  node: string,
  visited: Set<string> = new Set()
): void {
  // Si déjà visité, on s'arrête
  if (visited.has(node)) return;
 
  // On marque le nœud comme visité
  visited.add(node);
  console.log(node);
 
  // On explore récursivement chaque voisin
  const neighbors = graph.get(node) ?? [];
  for (const neighbor of neighbors) {
    dfs(graph, neighbor, visited);
  }
}
 
// Exemple d'utilisation
const graph: Graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["D", "E"]],
  ["C", []],
  ["D", []],
  ["E", []],
]);
 
dfs(graph, "A");
// Affiche : A, B, D, E, C

Vérifier si un chemin existe entre deux nœuds

function hasPath(
  graph: Graph,
  start: string,
  end: string,
  visited: Set<string> = new Set()
): boolean {
  if (start === end) return true;
  if (visited.has(start)) return false;
 
  visited.add(start);
 
  for (const neighbor of graph.get(start) ?? []) {
    if (hasPath(graph, neighbor, end, visited)) {
      return true;
    }
  }
 
  return false;
}

Détecter un cycle dans un graphe dirigé

function hasCycle(
  graph: Graph,
  node: string,
  visited: Set<string>,
  inStack: Set<string>
): boolean {
  visited.add(node);
  inStack.add(node);
 
  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      if (hasCycle(graph, neighbor, visited, inStack)) return true;
    } else if (inStack.has(neighbor)) {
      // On retombe sur un nœud encore dans la pile : cycle détecté
      return true;
    }
  }
 
  inStack.delete(node);
  return false;
}
 
function detectCycle(graph: Graph): boolean {
  const visited = new Set<string>();
  const inStack = new Set<string>();
 
  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      if (hasCycle(graph, node, visited, inStack)) return true;
    }
  }
 
  return false;
}

DFS vs BFS : lequel choisir ?

En résumé : DFS si vous voulez explorer tout un graphe ou trouver n'importe quel chemin. BFS si vous voulez trouver le plus court chemin.

Cas d'usage concrets

Résolution de labyrinthes : le DFS est naturellement adapté. Il fonce dans un couloir jusqu'au bout, revient si c'est sans issue, et tente une autre direction. Simple et efficace.

Détection de cycles : dans un graphe dirigé, le DFS peut détecter si un cycle existe en vérifiant si on retombe sur un nœud encore présent dans la pile d'appels courante (comme vu ci-dessus).

Tri topologique : pour ordonner des tâches avec des dépendances (ex. : "B dépend de A, C dépend de B"), le DFS permet de construire un ordre valide. On ajoute chaque nœud à une liste après avoir exploré tous ses voisins, puis on inverse.

Composantes connexes : pour savoir combien de "clusters" indépendants existent dans un graphe, on lance un DFS depuis chaque nœud non visité et on incrémente un compteur à chaque nouveau départ.

Résolution de puzzles : sudoku, n-reines, toute situation où on explore des possibilités et on fait marche arrière si ça ne convient pas.

Complexité

• Temps : O(V + E) — on visite chaque sommet (Vertex) une fois et on parcourt chaque arête (Edge) une fois.
• Espace : O(V) dans le pire cas, pour la pile d'appels et l'ensemble des nœuds visités.

Le piège à éviter : sur un graphe extrêmement profond (des milliers de niveaux), la récursion peut saturer la call stack. Dans ce cas, on peut réécrire le DFS de façon itérative avec une pile explicite (Array utilisé comme stack), ce qui donne exactement le même résultat sans risque de stack overflow.

Le DFS est l'un de ces algorithmes qu'on retrouve partout, souvent sans le savoir : dans les compilateurs, les moteurs de jeu, les résolveurs de dépendances. Maîtriser son principe, c'est avoir un outil fondamental dans sa boîte.