Graphes 04 : DFS, cycles et tri topologique

Pour inspecter un bâtiment, on peut terminer un couloir et toutes ses ramifications avant de revenir au croisement précédent. Le parcours en profondeur suit cette logique. Il ne cherche pas d'abord le trajet le plus court ; il révèle la structure des relations. Nous l'utiliserons pour former une forêt d'exploration, repérer des cycles et ordonner des tâches soumises à des dépendances.

1. Descendre puis revenir

La différence avec BFS tient à cette discipline. La file de BFS protège l'ordre des couches. La pile de DFS favorise la branche la plus récemment ouverte. Dans une version récursive, la pile est celle des appels de fonctions. Une version itérative peut conserver explicitement des cadres contenant le sommet courant et la position du prochain voisin à examiner.

Nous fixons l'ordre alphabétique des sommets de départ et des voisins. D'autres ordres produisent des arbres différents, sans rendre l'algorithme incorrect. Sur un graphe non connexe, il faut relancer DFS depuis chaque sommet encore inconnu pour parcourir l'ensemble. Ne pas effectuer cette relance limiterait l'étude à la seule partie accessible depuis la première racine.

2. Distinguer découverte et fin d'exploration

Explorer(u) :
    couleur[u] ← gris ; noter la découverte
    Pour chaque voisin v de u :
        Si couleur[v] = blanc :
            parent[v] ← u
            Explorer(v)
    couleur[u] ← noir ; noter la fin

Pour chaque sommet u :
    Si couleur[u] = blanc : Explorer(u)

Dans notre réseau non orienté, la branche de découverte est A–B–C–D–E–F. Les découvertes portent les dates 1 à 6 dans cet ordre. Les fins suivent l'ordre inverse : F finit à 7, E à 8, D à 9, C à 10, B à 11 et A à 12. Une branche doit se terminer avant que l'appel qui l'a ouverte puisse finir.

L'ordre de découverte coïncide ici avec celui de BFS, mais les parents sont différents. Cette coïncidence rappelle une règle importante : une simple liste de visites ne suffit pas toujours à identifier l'algorithme utilisé. Les dates, la file ou la pile et les relations de parenté montrent le mécanisme réel.

3. Détecter un cycle sans faux positif

Sur notre réseau, C voit A alors que A est encore gris. La branche A–B–C et l'arête CA forment un cycle. En revanche, quand B voit A juste après avoir été découvert depuis A, il examine simplement l'autre occurrence de la même arête non orientée. Sans exception pour le parent, toute arête serait interprétée à tort comme un cycle.

Cette exception suppose un graphe simple. Avec plusieurs arêtes parallèles, il faut identifier l'arête précise utilisée pour découvrir le sommet, plutôt qu'ignorer toutes les liaisons vers le parent. Une seconde arête parallèle peut apporter une information réelle. La version du pseudo-code et les hypothèses sur les données doivent donc rester cohérentes.

Dans un graphe orienté, un arc vers un sommet noir ne prouve pas à lui seul un cycle : l'exploration de ce sommet est déjà terminée et la branche active n'y remonte pas nécessairement. Le test utile concerne les sommets gris. On peut mémoriser les parents pour reconstituer le cycle lorsque ce test réussit.

4. Compter les composantes : le sens des flèches compte

Pour un graphe non orienté, chaque relance de DFS depuis un sommet inconnu découvre exactement une nouvelle composante connexe. On attribue le même numéro à tous les sommets découverts pendant cette relance. Il n'existe pas de liaison entre deux composantes, sinon la première exploration aurait traversé cette liaison.

Dans un graphe orienté, compter les racines de la forêt ne donne ni automatiquement les composantes fortement connexes, ni les composantes obtenues en oubliant les flèches. Une exploration peut atteindre un sommet sans pouvoir revenir. Les algorithmes de Kosaraju ou de Tarjan ajoutent des informations pour résoudre la forte connexité. Nous en retenons ici la définition et la distinction, sans prétendre la calculer avec le simple comptage des racines.

5. Ordonner des tâches avec le tri topologique

Considérons les dépendances AC, AD, BD, CE, DE et EF. Les lettres désignent cette fois des tâches. Une tâche placée au début n'est pas forcément plus importante : elle satisfait simplement les dépendances disponibles. Avec notre ordre de visite, DFS découvre A, C, E, F, D, puis B. La liste des fins est F, E, C, D, A, B.

Inverser ces fins donne B, A, D, C, E, F. On vérifie chaque arc : A précède C et D, B précède D, C et D précèdent E, puis E précède F. Cet ordre est valide même si l'ordre alphabétique A, B, C, D, E, F en serait également un. Il peut exister plusieurs réponses correctes.

Pourquoi inverser les fins ? Pour un arc u → v, soit v est exploré depuis u et finit avant lui, soit v avait déjà fini lorsque l'arc est examiné. Le cas où v est gris révélerait un cycle, interdit dans un DAG. Dans tous les cas autorisés, u se place donc avant v dans l'ordre inverse des fins. Si un cycle est détecté, il faut refuser le classement au lieu de présenter une liste trompeuse.

6. Évaluer les ressources et les limites

Avec des listes d'adjacence, chaque sommet change de couleur un nombre constant de fois et chaque entrée de voisinage est examinée une fois. DFS coûte O(n + m), comme le tri topologique qui lui ajoute l'inversion des fins. Les couleurs, les parents, les dates et la pile utilisent O(n) de mémoire auxiliaire.

La profondeur de la pile peut atteindre n sur une longue chaîne. Dans une implantation réelle, la récursion peut dépasser la limite du langage bien avant d'épuiser la mémoire théorique disponible. Une pile explicite évite cette limite particulière. Pour conserver exactement les dates de fin, elle doit mémoriser où reprendre l'énumération des voisins ; empiler seulement des sommets puis les marquer ne reproduit pas automatiquement la trace récursive.

Exercices corrigés

Voir le programme complet · Faire les 30 exercices du TD