Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

De l'exploration de grotte au code
visited.add(node)🧵 Marquer ce tunnel comme exploré
for neighbor in graph[node]:🔀 Regarder chaque tunnel qui part d'ici
depth_first(neighbor, visited)⬇️ S'enfoncer dans le premier tunnel inexploré
return order↩️ Cul-de-sac : remonter la ficelle
Allez d'abord au fond, puis revenez sur vos pas et essayez la branche suivante.
En une phrase

Le 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

  1. visited.add(node) marque le nœud : un cycle ne peut donc pas provoquer une récursivité sans fin.
  2. for neighbor in graph[node]: regarde chaque voisin, l'un après l'autre.
  3. order.extend(depth_first(neighbor, visited)) explore toute la branche sous un voisin avant le suivant.
  4. 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

Exécuter le code →
main.py
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"))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Utiliser un argument par défaut mutable

visited=set() serait partagé entre des appels indépendants.

Problème
def depth_first(node, visited=set()):
Correction
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.

Tous les défis