Le parcours en profondeur (DFS) en Python
Dans cette leçon, vous allez parcourir un graphe avec le parcours en profondeur, implémenté par une fonction récursive.
Introduction
Le problème
Pour trouver la sortie d'un labyrinthe, vérifier si un graphe contient un cycle ou ordonner des tâches qui dépendent les unes des autres, il faut à chaque fois suivre un chemin jusqu'au bout avant d'en essayer un autre. C'est le parcours en profondeur.
Imaginez-le ainsi
Le parcours en profondeur, c'est explorer une grotte avec une pelote de ficelle. Vous suivez un tunnel jusqu'au bout. Arrivé dans un cul-de-sac, vous remontez la ficelle jusqu'à la dernière bifurcation et vous essayez le tunnel suivant. Vous marquez les tunnels explorés pour ne jamais y passer deux fois.
visited.add(node)🧵 Marquer ce tunnel comme exploréfor neighbor in graph[node]:🔀 Regarder chaque tunnel qui part d'icidepth_first(neighbor, visited)⬇️ S'enfoncer dans le premier tunnel inexploréreturn order↩️ Cul-de-sac : remonter la ficelleLe parcours en profondeur (DFS) explore un graphe en suivant une branche aussi loin que possible avant de revenir en arrière, le plus souvent par récursivité ou avec une pile.
Points clés
visited.add(node)marque le nœud : un cycle ne peut donc pas provoquer une récursivité sans fin.for neighbor in graph[node]:regarde chaque voisin, l'un après l'autre.order.extend(depth_first(neighbor, visited))explore toute la branche sous un voisin avant le suivant.- Dans le résultat, D est visité avant C, car la branche de B est explorée jusqu'au bout en premier.
Quand l’utiliser ?
- Trouver un chemin quelconque, résoudre des labyrinthes et des énigmes par retour arrière.
- Détecter des cycles et ordonner des tâches avec dépendances (tri topologique).
- Explorer toutes les parties connexes d'un graphe.
Quand s'en passer
- Vous avez besoin du plus court chemin : le parcours en profondeur peut trouver d'abord un long chemin ; utilisez le parcours en largeur.
- Les graphes très profonds : la récursivité peut atteindre la limite de Python ; utilisez une pile explicite.
Visualisation de Le parcours en profondeur (DFS) en Python
O(V + E)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))
Résultat de l’exécution
['A', 'B', 'D', 'C', 'E']
Explication du code
L'ensemble visited mémorise les sommets visités pour éviter les doublons et les boucles infinies quand le graphe contient des cycles. Chaque appel récursif descend dans un voisin pas encore visité, le programme visite donc A, B, D avant de revenir visiter C et E. La pile d'appels joue le rôle de la pile de l'algorithme, et la complexité est O(V + E).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Utiliser un argument par défaut mutable
visited=set() serait partagé entre des appels indépendants.
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Count Islands Count groups of connected land cells in a grid. Moyen
- Composantes fortement connexes Comptez les groupes de nœuds pouvant tous s’atteindre mutuellement. Difficile
- Longest Path in a DAG Find the heaviest path in a task dependency graph. Difficile