Parcourir un graphe en profondeur : DFS

Fixer l’ordre des voisins

Considérons le graphe non orienté avec les liaisons A-B, A-C, B-D, B-E et C-E. Le sommet F est isolé. Nous traiterons les voisins dans l’ordre alphabétique. Sans cet ordre, plusieurs parcours en profondeur peuvent être corrects ; une séquence ne doit pas être déclarée fausse simplement parce qu’elle suit un autre choix autorisé.

En partant de A, on découvre B, puis D. D ne possède pas de voisin inconnu, donc on revient à B. On découvre ensuite E, puis C. Depuis C, tous les voisins sont déjà découverts. La séquence de première découverte est A,B,D,E,C.

Marquer avant d’explorer davantage

Un sommet doit être marqué comme visité dès sa découverte. Lorsque ses voisins sont examinés, les sommets déjà visités sont ignorés pour les nouveaux appels. Cela empêche de tourner entre deux voisins d’un graphe non orienté ou de parcourir indéfiniment un cycle.

def profondeur(graphe, sommet, visites):
    visites.add(sommet)
    for voisin in graphe[sommet]:
        if voisin not in visites:
            profondeur(graphe, voisin, visites)

L’ensemble visites est partagé volontairement entre les appels : il représente les découvertes de tout le parcours. En créer un nouveau vide à chaque appel ferait perdre cette mémoire globale et pourrait réintroduire des visites infinies.

Le test doit avoir lieu avant l’appel récursif, et le marquage avant la visite des voisins. Pour chaque sommet découvert, une seule exploration de son voisinage sera donc engagée. Sur une arête non orientée, l’autre extrémité retrouvera le parent dans ses voisins, mais reconnaîtra son marquage.

Comprendre les retours et la pile

La récursion conserve implicitement les sommets dont certains voisins restent à examiner. Une version itérative peut utiliser une pile explicite. Pour reproduire exactement l’ordre d’une version récursive, il faut préciser quand les sommets sont marqués et dans quel ordre les voisins sont empilés : une pile inverse l’ordre de retrait.

Il existe donc plusieurs variantes correctes de DFS. Une trace doit correspondre à l’algorithme réellement donné. Le retour à un sommet ne signifie pas qu’il est découvert une deuxième fois ; il permet de poursuivre l’exploration de ses voisins encore inconnus.

Ce que le parcours permet de conclure

Depuis A, le parcours atteint les sommets accessibles par des liaisons, mais pas F, qui est isolé. Pour visiter tout un graphe éventuellement non connexe, on relance le parcours depuis chaque sommet encore inconnu. On obtient alors une forêt de parcours.

DFS peut servir à rechercher un chemin, explorer une composante ou contribuer à détecter des cycles. Le premier chemin trouvé n’est pas nécessairement celui qui utilise le moins d’arêtes. Avec des listes d’adjacence, chaque sommet et chaque liaison sont examinés un nombre borné de fois ; le travail est de l’ordre du nombre de sommets plus celui des arêtes.

Exemple suivi : découvrir puis revenir

Reprenons le départ A. Les premières piles actives sont [A], [A,B], [A,B,D]. Après traitement de D, la pile redevient [A,B] et B reprend au voisin suivant, E. On obtient [A,B,E], puis [A,B,E,C]. C voit A et E déjà marqués et ne crée aucun appel supplémentaire. Les retours retirent ensuite C, E, B puis A. La liste des découvertes reste A,B,D,E,C.

Cette trace distingue trois informations : l’ensemble des sommets déjà rencontrés, l’ordre de leur première découverte et la pile des appels non terminés. D reste visité après avoir disparu de la pile. E est accessible depuis A par A-B-E, mais l’ordre des découvertes A,B,D,E n’est pas lui-même un chemin : D et E ne sont pas reliés directement. Pour donner un chemin, il faut conserver les parents de découverte ou vérifier chaque liaison.

Exemple suivi : explorer une autre composante

Le sommet F n’a aucun voisin. Un appel depuis F le marque, constate son voisinage vide et revient. Il découvre exactement un sommet ; il ne conclut rien sur les chemins entre A, B, C, D et E. Pour parcourir tout le graphe, une boucle extérieure examine les sommets et lance DFS seulement pour ceux qui ne sont pas encore marqués. Depuis A puis F, elle produit deux arbres de parcours, correspondant ici aux deux composantes connexes.

Dans un graphe orienté, on suit uniquement les successeurs : le résultat décrit les sommets accessibles dans ce sens. Pour comparer deux traces, annoncez également la stratégie d’empilement d’une version itérative. Empiler A puis B fait retirer B avant A ; une simple inversion des voisins peut changer l’ordre observé. Les garanties essentielles restent l’exploration des sommets accessibles et l’absence de redécouvertes, sous réserve d’un ensemble partagé et d’une représentation fidèle du graphe.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Oublier de marquer les sommets.

Les cycles et les retours d’arêtes peuvent provoquer des répétitions infinies.

Attendre un plus court chemin de DFS.

La profondeur privilégie une branche, pas les distances par couches.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Métropole · Jour 1 : Recto-Verso : jouer avec XOR et chercher la victoire dans un graphe
• Bac 2026 · Centres étrangers groupe 1 · Jour 1 : Démineur : voisinage, propagation et scores en ligne
• Bac 2026 · Asie · Jour 2 : Jeu de mots : déduire un alphabet par tri topologique
• Bac 2026 · Polynésie · Jour 2 : Taquin et recherche de texte : deux parcours à ne pas interrompre trop tôt

Le prochain pas

• Parcourir un graphe en largeur : BFS
• Chercher des chemins et détecter des cycles

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.