Implémentation de DFS (récursif et itératif)

1. L'intuition du parcours en profondeur

Si le BFS explore le graphe comme une onde qui se propage, le DFS se comporte plutôt comme un explorateur dans un labyrinthe qui suit un chemin jusqu'à une impasse, puis revient à la dernière intersection pour essayer une autre voie.

Pour visualiser cette philosophie, la vidéo suivante propose une excellente démonstration intuitive.

Cette stratégie "plonge d'abord" est rendue possible en changeant simplement la structure de données utilisée pour stocker les sommets à visiter : au lieu de la file (FIFO) du BFS, le DFS utilise une pile (LIFO - Last-In, First-Out).

2. L'implémentation itérative avec une pile explicite

Commençons par la version itérative, qui rend l'utilisation de la pile explicite. Le principe est très proche de celui du BFS, mais le comportement est radicalement différent.

Algorithme DFS itératif :

1. Initialiser une pile vide et y empiler le sommet de départ s.
2. Initialiser un ensemble visite pour marquer les sommets déjà traités.
3. Tant que la pile n'est pas vide :
   a. Dépiler un sommet u.
   b. Si u n'a pas été visité :
   i. Marquer u comme visité.
   ii. Traiter u (par exemple, l'ajouter à une liste de résultats).
   iii. Pour chaque voisin v de u, empiler v sur la pile.

Le fait d'empiler les voisins et de toujours traiter le sommet au sommet de la pile garantit que l'on explore le plus récemment découvert en premier, nous menant ainsi en profondeur.

La vidéo suivante illustre parfaitement ce mécanisme.

Implémentation en Python

En Python, une simple liste (list) peut servir de pile, en utilisant les méthodes append() pour empiler et pop() pour dépiler.

def dfs_iterative(graph, start_node):



    # graph: dictionnaire {sommet: [voisins]}
    
    stack = [start_node]
    visited = set()
    traversal_order = []

    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            



            # Empiler les voisins. Notez que l'ordre d'ajout peut changer le parcours.
            # Inverser les voisins pour un parcours plus "naturel" (ex: de gauche à droite)
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)
                    
    return traversal_order

Note : L'instruction reversed() est une astuce. Si les voisins d'un sommet sont [B, C] et que vous les empilez dans cet ordre (B puis C), C sera traité avant B. Inverser la liste des voisins avant de les empiler permet souvent d'obtenir un parcours qui correspond à celui de la version récursive, plus intuitive.

3. L'implémentation récursive : l'élégance de la pile implicite

La nature du DFS se prête magnifiquement à une formulation récursive. La complexité de la gestion de la pile est alors déléguée au système, via ce qu'on appelle la pile d'appels (ou call stack).

Chaque fois que vous appelez une fonction, ses informations (variables locales, point de retour) sont empilées sur la pile d'appels. Lorsqu'une fonction se termine, elle est dépilée. Un appel récursif consiste donc à empiler une nouvelle instance de la même fonction. C'est exactement le comportement LIFO dont nous avons besoin.

Algorithme DFS récursif :

fonction DFS_rec(graphe, sommet_u, visite):
    marquer sommet_u comme visité
    traiter sommet_u

    pour chaque voisin v de sommet_u:
        si v n'a pas été visité:
            DFS_rec(graphe, v, visite)

C'est tout. La "pile" est gérée implicitement par les appels récursifs imbriqués.

La vidéo suivante explique remarquablement ce lien fondamental entre récursivité et pile d'appels, avant de l'appliquer au DFS.

Implémentation en Python

La version récursive est souvent plus concise et considérée comme plus élégante.

def dfs_recursive(graph, start_node):



    # graph: dictionnaire {sommet: [voisins]}
    
    visited = set()
    traversal_order = []

    def _dfs_util(node):
        visited.add(node)
        traversal_order.append(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                _dfs_util(neighbor)

    _dfs_util(start_node)
    return traversal_order

4. Synthèse et comparaison formelle

Pour une préparation à l'Agrégation, il est important de pouvoir se référer à des descriptions formelles.

Récursif ou Itératif ?

La complexité du DFS, quelle que soit l'implémentation, est de $O(|S|+|A|)$ (ou $O(n+m)$ où $n$ est le nombre de sommets et $m$ le nombre d'arêtes), car chaque sommet est visité une fois et chaque arête est traversée une fois (deux fois pour un graphe non orienté).

5. Exercice d'application

Appliquons maintenant nos connaissances. Considérons le graphe orienté suivant :

Le graphe peut être représenté par la liste d'adjacence suivante :
graph = {0: [1, 2], 1: [], 2: [3, 4], 3: [4], 4: []}

Votre tâche (15 minutes) :

1. Trace itérative : En partant du sommet 0, déroulez l'algorithme DFS itératif. À chaque itération de la boucle while, notez :

   • Le sommet dépilé.
   • L'état de la pile après avoir ajouté les voisins.
   • L'ensemble des sommets visités.
   • Quel sera l'ordre de parcours final (traversal_order) ?

2. Trace récursive : En partant du sommet 0, déroulez l'algorithme DFS récursif. Montrez la séquence des appels récursifs (par exemple, _dfs_util(0) appelle _dfs_util(1) qui retourne, puis _dfs_util(0) appelle _dfs_util(2), etc.).

   • Quel sera l'ordre de parcours final ? Est-il identique à celui de la version itérative (avec l'astuce reversed) ?

Prenez le temps de faire cet exercice sur papier. Il est essentiel pour solidifier votre compréhension des deux mécanismes.

Conclusion

Le parcours en profondeur est un algorithme aussi fondamental que le BFS, mais avec un caractère très différent. Sa capacité à s'enfoncer dans le graphe en fait un outil de choix pour de nombreuses applications.

Points clés à retenir :

• Le DFS explore un graphe en suivant une branche jusqu'au bout avant de revenir en arrière.
• Il s'appuie sur une structure de données LIFO (pile).
• L'implémentation itérative utilise une pile explicite (une liste en Python).
• L'implémentation récursive, souvent plus élégante, utilise la pile d'appels implicite du système.
• Les deux approches ont la même complexité $O(|S|+|A|)$ mais des compromis différents en termes d'écriture et de robustesse (risque de stack overflow pour la récursivité).

Prochaine étape :
Maintenant que nous maîtrisons le mécanisme du DFS, nous allons l'utiliser pour résoudre un premier problème classique : la détection de cycles dans un graphe orienté. Nous verrons comment une simple modification du marquage des sommets (en utilisant des couleurs) pendant le parcours nous permet d'identifier efficacement les "retours en arrière" qui signalent la présence d'un cycle.