Tri topologique par DFS et détection de cycle

Contexte et définitions

Un tri topologique est un ordre linéaire des sommets d'un graphe orienté acyclique (DAG, Directed Acyclic Graph) tel que pour toute arête 
(
𝑢
,
𝑣
)
(u,v), le sommet 
𝑢
u apparaît avant 
𝑣
v dans l'ordre. Si le graphe contient un cycle, aucun tri topologique n'existe.

La détection de cycle n'est pas une passe séparée : elle s'intègre directement au parcours DFS, qui produit soit un ordre topologique, soit la preuve qu'un cycle existe.

Algorithme de tri topologique par DFS

2.1. Initialisation
Marquage des sommets (couleurs) :
Blanc : sommet non visité.
Gris : sommet en cours de visite (découvert, exploration non terminée) — il est dans la pile d'appels récursive.
Noir : sommet entièrement exploré (toutes ses arêtes sortantes ont été traitées).
Pile de résultats : les sommets y sont empilés après exploration complète de leurs successeurs.

2.2. Parcours DFS modifié
Pour chaque sommet 
𝑢
u non visité :

Marquer 
𝑢
u en gris.
Pour chaque successeur 
𝑣
v de 
𝑢
u :

Si 
𝑣
v est blanc : appel récursif du DFS sur 
𝑣
v.
Si 
𝑣
v est gris : cycle détecté (
𝑣
v est un ancêtre de 
𝑢
u dans l'arbre DFS courant — arête arrière).
Si 
𝑣
v est noir : l'arête 
(
𝑢
,
𝑣
)
(u,v) est une arête « avant » ou « transversale », sans effet sur le tri.

Marquer 
𝑢
u en noir et l'empiler.

2.3. Résultat
Sans cycle : la pile lue de haut en bas (c.-à-d. l'ordre d'empilement inversé) donne un ordre topologique valide.
Avec cycle : le graphe n'est pas un DAG, aucun tri topologique n'existe.

Justification : un sommet est empilé seulement lorsque tous ses successeurs le sont déjà ; il se retrouve donc avant eux après inversion.

Détection de cycle

𝑣
v gris signifie que 
𝑣
v est encore actif dans la pile d'appels.
Rencontrer un sommet gris 
𝑣
v en explorant les successeurs de 
𝑢
u signifie que 
𝑣
v est un ancêtre de 
𝑢
u, formant le cycle 
𝑣
→
⋯
→
𝑢
→
𝑣
v→⋯→u→v.
Attention : le simple test « déjà visité » ne suffit pas ; il faut distinguer gris (cycle) de noir (pas de cycle).

Exemple : dans 
𝐴
→
𝐵
→
𝐶
→
𝐴
A→B→C→A :

𝐴
A gris, puis 
𝐵
B gris, puis 
𝐶
C gris ;

𝐶
C a pour successeur 
𝐴
A, qui est gris cycle détecté.

Complexité

Temps : 
𝑂
(
𝑉
+
𝐸
)
O(V+E) (identique à un DFS classique).
Espace : 
𝑂
(
𝑉
)
O(V) pour les couleurs, la pile de résultats et la pile d'appels.

Pseudocode

def tri_topologique(graphe):
couleur = {} Blanc: 0, Gris: 1, Noir: 2
ordre = [] Pile pour le résultat
cycle = False

def dfs(u):
nonlocal cycle
couleur[u] = 1 Gris
for v in graphe[u]:
c = couleur.get(v, 0)
if c == 0: Blanc
dfs(v)
elif c == 1: Gris -> arête arrière
cycle = True
couleur[u] = 2 Noir
ordre.append(u)

for u in graphe:
if couleur.get(u, 0) == 0:
dfs(u)
if cycle:
return None Cycle détecté : pas de tri topologique

return ordre[::-1] Inversion de la pile

Exemple concret

Graphe : arêtes 
𝐴
→
𝐵
A→B, 
𝐴
→
𝐶
A→C, 
𝐵
→
𝐷
B→D, 
𝐶
→
𝐷
C→D.

A B D

C

Étapes du DFS depuis 
𝐴
A :

𝐴
A gris successeur 
𝐵
B (blanc).
𝐵
B gris successeur 
𝐷
D (blanc).
𝐷
D gris, aucun successeur 
𝐷
D noir, empilé.
Retour en 
𝐵
B : plus de successeur 
𝐵
B noir, empilé.
Retour en 
𝐴
A : successeur 
𝐶
C (blanc) 
𝐶
C gris.
𝐶
C explore 
𝐷
D (noir) : arête transversale, rien à faire 
𝐶
C noir, empilé.
𝐴
A noir, empilé.

Pile (ordre d'empilement) : 
[
𝐷
,
𝐵
,
𝐶
,
𝐴
]
[D,B,C,A]
Ordre topologique (pile inversée) : 
[
𝐴
,
𝐶
,
𝐵
,
𝐷
]
[A,C,B,D]

[
𝐴
,
𝐵
,
𝐶
,
𝐷
]
[A,B,C,D] est également valide : le tri topologique n'est pas unique.

Cas avec cycle

Graphe : 
𝐴
→
𝐵
→
𝐶
→
𝐴
A→B→C→A
Lors du DFS, 
𝐶
C explore 
𝐴
A, qui est gris cycle détecté, l'algorithme renvoie l'absence de tri.

Applications

Ordonnancement de tâches (compilation de fichiers avec dépendances, make).
Résolution de dépendances (gestionnaires de paquets).
Planification de projets (méthode PERT/CPM).

Résumé :
Le tri topologique par DFS empile chaque sommet après traitement complet de ses successeurs, puis inverse la pile.
La détection de cycle repose sur la rencontre d'un sommet gris (arête arrière) pendant le DFS.
Si un cycle existe, le tri est impossible.