Parcours en profondeur (DFS)
Dernière mise à jour
Le parcours en profondeur explore un graphe en allant le plus loin possible le long de chaque branche avant de revenir en arrière. En partant d'un nœud source, il visite un voisin, puis le voisin de ce voisin, et ainsi de suite jusqu'à atteindre une impasse (un nœud sans voisin non visité), moment auquel il revient en arrière et essaie la branche suivante. Appuyez sur lecture ci-dessus pour le voir descendre le long d'un chemin, atteindre le fond et remonter.
Le DFS s'exprime naturellement avec une pile : soit une pile explicite (comme animée ici), soit la pile d'appels via la récursion. Il visite chaque nœud et chaque arête une fois, donc il s'exécute en temps O(V + E) pour un graphe à V sommets et E arêtes.
Complexité en temps et en espace
| Mesure | Complexité | Remarques |
|---|---|---|
| Temps | O(V + E) | Chaque sommet et arête visité une fois |
| Espace | O(V) | Pile + ensemble des visités, au pire tous les nœuds |
| Parcours | Le plus profond d'abord | Suit une branche jusqu'au bout avant les autres |
| Structure de données | Pile (ou récursion) | L'ordre LIFO pilote le comportement en profondeur |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Empiler le nœud source sur la pile. |
| 2 | Dépiler un nœud ; s'il est déjà visité, le sauter. |
| 3 | Le marquer comme visité et enregistrer l'arête qui l'a atteint. |
| 4 | Empiler tous ses voisins non visités. |
| 5 | Répéter jusqu'à ce que la pile soit vide. |
Exemple détaillé
DFS itératif depuis A sur le graphe A → [B, C], B → [D], C → [E], en empilant les voisins dans l'ordre indiqué (la pile LIFO dépile d'abord le dernier empilé) :
| Étape | Pile (sommet à droite) | Visités | Action |
|---|---|---|---|
| 1 | [A] | {} | Empiler la source A. |
| 2 | [B, C] | {A} | Dépiler A, marquer visité, empiler les voisins B puis C. |
| 3 | [B, E] | {A, C} | Dépiler C, marquer visité, empiler le voisin E. |
| 4 | [B] | {A, C, E} | Dépiler E, marquer visité, aucun voisin. |
| 5 | [D] | {A, C, E, B} | Dépiler B, marquer visité, empiler le voisin D. |
| 6 | [] | {A, C, E, B, D} | Dépiler D, marquer visité, pile vide : terminé. |
Quand utiliser le DFS
| À utiliser quand | À éviter quand |
|---|---|
| Vous avez besoin de détecter des cycles, d'un tri topologique ou de trouver les composantes connexes. | Vous avez besoin du plus court chemin dans un graphe non pondéré : c'est le BFS qui le fait, pas le DFS. |
| Le graphe est large et peu profond, donc une pile utilise bien moins de mémoire qu'une file remplie de nombreux nœuds frontière. | Le graphe est très profond et vous utilisez la récursion : la pile d'appels peut déborder. |
| Vous voulez explorer les chemins de manière exhaustive, comme pour résoudre un labyrinthe ou une recherche avec retour arrière. | Vous avez besoin de découvrir les nœuds par ordre de distance depuis la source. |
| Vous vérifiez l'accessibilité ou l'existence d'un chemin entre deux nœuds. | Vous devez garantir le nombre minimal d'arêtes sur le chemin trouvé. |
Code de Depth-First Search
Une implémentation propre et exécutable de Depth-First Search en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Depth-First Search en Python
Python
1def dfs(graph, node, visited):2 visited.add(node)3 order = [node]4 for neighbor in graph[node]:5 if neighbor not in visited:6 order.extend(dfs(graph, neighbor, visited))7 return order8
9
10graph = {11 "A": ["B", "C"],12 "B": ["D", "E"],13 "C": ["F"],14 "D": [],15 "E": ["F"],16 "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))Code de Depth-First Search en JavaScript
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11 if (visited.has(node)) return order;12 visited.add(node);13 order.push(node);14 for (const next of graph[node]) {15 dfs(next, visited, order);16 }17 return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));Code de Depth-First Search en Java
Java
1import java.util.List;2
3public class Main {4 static List<List<Integer>> adj = List.of(5 List.of(1, 2), // neighbors of 06 List.of(0, 3, 4), // neighbors of 17 List.of(0, 5), // neighbors of 28 List.of(1),9 List.of(1, 5),10 List.of(2, 4)11 );12 static boolean[] visited = new boolean[6];13
14 static void dfs(int node) {15 visited[node] = true;16 System.out.print(" " + node);17 for (int next : adj.get(node)) {18 if (!visited[next]) dfs(next);19 }20 }21
22 public static void main(String[] args) {23 System.out.print("DFS from 0:");24 dfs(0);25 System.out.println();26 }27}Code de Depth-First Search en C++
C++
1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5 std::vector<bool>& visited) {6 visited[node] = true;7 std::cout << node << " ";8 // Recurse into every unvisited neighbor9 for (int next : adj[node]) {10 if (!visited[next]) dfs(next, adj, visited);11 }12}13
14int main() {15 // 6-node undirected graph as an adjacency list16 std::vector<std::vector<int>> adj = {17 {1, 2}, // 018 {0, 3, 4}, // 119 {0, 5}, // 220 {1}, // 321 {1, 5}, // 422 {2, 4}, // 523 };24 std::vector<bool> visited(adj.size(), false);25 std::cout << "DFS from node 0: ";26 dfs(0, adj, visited);27 std::cout << "\n";28 return 0;29}Code de Depth-First Search en C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8 {0, 1, 1, 0, 0, 0},9 {1, 0, 0, 1, 1, 0},10 {1, 0, 0, 0, 0, 1},11 {0, 1, 0, 0, 0, 0},12 {0, 1, 0, 0, 0, 1},13 {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18 visited[node] = true;19 printf("%d ", node);20 // Recurse into every unvisited neighbor21 for (int next = 0; next < N; next++) {22 if (adj[node][next] && !visited[next]) dfs(next);23 }24}25
26int main(void) {27 printf("DFS from node 0: ");28 dfs(0);29 printf("\n");30 return 0;31}FAQ sur le parcours en profondeur
Quelle est la complexité temporelle du DFS ?
Le DFS s'exécute en temps
O(V + E), où V est le nombre de sommets et E le nombre d'arêtes, car il visite chaque sommet une fois et examine chaque arête une fois. Il utilise un espace O(V) pour la pile et l'ensemble des visités.Quelle est la différence entre DFS et BFS ?
Le DFS utilise une pile et plonge en profondeur le long d'une branche avant de revenir en arrière, tandis que le BFS utilise une file et explore niveau par niveau, les nœuds les plus proches d'abord. Le BFS trouve le plus court chemin dans un graphe non pondéré ; le DFS non, mais il utilise moins de mémoire sur les graphes larges et convient naturellement à des tâches comme la détection de cycles et le tri topologique.
Le DFS est-il récursif ou itératif ?
Les deux fonctionnent. La version récursive utilise implicitement la pile d'appels du programme et est très concise ; la version itérative utilise une pile explicite (comme l'animation ici) et évite les débordements de pile dus à une récursion profonde sur les grands graphes.
Quand dois-je utiliser le DFS plutôt que le BFS ?
Utilisez le DFS quand vous devez explorer des chemins entiers : détection de cycles, tri topologique, composantes connexes ou recherche avec retour arrière comme la résolution d'un labyrinthe. Il utilise aussi moins de mémoire sur les graphes larges, car la pile ne contient que la frontière d'une seule branche à la fois. Optez pour le BFS lorsque vous avez besoin du plus court chemin dans un graphe non pondéré ou des nœuds par ordre de distance depuis la source.
Le DFS peut-il trouver le plus court chemin ?
Pas de façon fiable. Le DFS renvoie le premier chemin qu'il trouve, qui n'est souvent pas celui comptant le moins d'arêtes, car il s'engage à plonger en profondeur plutôt qu'à s'étendre uniformément. Pour les plus courts chemins dans un graphe non pondéré, utilisez le BFS, et pour les graphes pondérés, utilisez l'algorithme de Dijkstra.
Pourquoi le DFS a-t-il besoin d'un ensemble de visités ?
Sans ensemble de visités, le DFS revisitera les nœuds accessibles par plusieurs chemins et, dans un graphe cyclique, bouclera à l'infini. Marquer un nœud comme visité au moment de le dépiler (et sauter les dépilements déjà visités) garantit que chaque nœud est traité une fois et maintient le temps d'exécution à
O(V + E). Une erreur fréquente consiste à ne marquer les nœuds comme visités qu'au dépilement tout en continuant d'empiler des doublons, ce qui est correct mais peut laisser des entrées périmées dans la pile qu'il faut sauter.Ressources associées
Plus de visualisations
