04 — Détection de cycle et graphes acycliques (DAG)

Ce que tu vas apprendre

• Pourquoi détecter un cycle est une question fréquente et utile
• Détecter un cycle dans un graphe orienté (coloration des sommets)
• Détecter un cycle dans un graphe non orienté
• Ce qu'est un DAG et pourquoi cette structure compte

Prérequis

• 03 — Le parcours en profondeur (DFS)

Détecter un cycle dans un graphe répond à des questions très concrètes : y a-t-il une dépendance circulaire entre mes modules ? Un deadlock potentiel entre des processus qui s'attendent mutuellement ? Une boucle infinie dans une chaîne de tâches ? Le DFS de l'article précédent fournit la réponse, mais la méthode diffère selon que le graphe est orienté ou non. Et l'absence de cycle définit une structure capitale, le DAG.

Détecter un cycle dans un graphe orienté

Dans un graphe orienté, un cycle est un chemin qui suit le sens des arêtes et revient à son point de départ (A→B→C→A). La détection repose sur une idée fine : pendant le DFS, on distingue les sommets selon trois états, souvent appelés trois couleurs.

• Blanc : pas encore visité.
• Gris : en cours de visite (dans la branche d'exploration actuelle, sur la pile de récursion).
• Noir : entièrement traité (lui et tous ses descendants).

Le cycle se détecte quand le DFS rencontre un sommet gris : cela veut dire qu'on revient sur un sommet qui est encore dans la branche courante, donc on a bouclé. Rencontrer un sommet noir n'est pas un cycle, c'est juste un sommet déjà exploré par un autre chemin.

pythonBLANC, GRIS, NOIR = 0, 1, 2

def a_un_cycle_oriente(graphe):
    couleur = {s: BLANC for s in graphe}

    def visiter(sommet):
        couleur[sommet] = GRIS
        for voisin in graphe[sommet]:
            if couleur[voisin] == GRIS:        # retour sur la branche : cycle
                return True
            if couleur[voisin] == BLANC and visiter(voisin):
                return True
        couleur[sommet] = NOIR                 # entièrement traité
        return False

    return any(couleur[s] == BLANC and visiter(s) for s in graphe)

La distinction gris/noir est essentielle. Un piège fréquent est de marquer simplement « visité » sans distinguer les deux états : on détecte alors de faux cycles dès qu'un sommet a deux chemins entrants, ce qui n'est pas un cycle.

Détecter un cycle dans un graphe non orienté

Dans un graphe non orienté, chaque arête se parcourt dans les deux sens, donc revenir vers le sommet d'où l'on vient n'est pas un cycle. La règle change : il y a un cycle si le DFS atteint un sommet déjà visité qui n'est pas le parent direct du sommet courant.

pythondef a_un_cycle_non_oriente(graphe):
    visites = set()

    def visiter(sommet, parent):
        visites.add(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:
                if visiter(voisin, sommet):
                    return True
            elif voisin != parent:   # déjà vu, et ce n'est pas d'où je viens
                return True
        return False

    return any(s not in visites and visiter(s, None) for s in graphe)

Pour le graphe non orienté, union-find (série Structures de données) est une alternative élégante : on ajoute les arêtes une par une, et si une arête relie deux sommets déjà dans le même groupe, elle ferme un cycle.

Le DAG

Un graphe orienté sans aucun cycle s'appelle un DAG (Directed Acyclic Graph). Cette structure est partout, parce qu'elle modélise les relations de dépendance et d'antériorité qui, par nature, ne peuvent pas boucler.

• Dépendances de build : un module dépend d'autres modules ; une dépendance circulaire est une erreur. Les systèmes de build vérifient que le graphe est un DAG.
• Dépendances de paquets : npm, pip et leurs semblables refusent (ou gèrent à part) les cycles.
• Planification de tâches : « cette tâche doit finir avant cette autre » forme un DAG.
• Pipelines de données et calcul : les graphes de calcul (build systems, workflows, certains moteurs de machine learning) sont des DAG.
• git : l'historique des commits est un DAG (chaque commit pointe vers ses parents).

La propriété clé du DAG : comme il n'a pas de cycle, on peut ordonner ses sommets de façon que chaque arête aille toujours « vers l'avant ». C'est-à-dire qu'on peut trouver un ordre où chaque tâche vient après toutes celles dont elle dépend. Cet ordonnancement s'appelle le tri topologique, et il n'existe que pour les DAG : s'il y a un cycle, aucun ordre n'est possible (A dépend de B qui dépend de A).

Détecter un cycle et faire un tri topologique sont donc les deux faces d'une même pièce : avant d'ordonner des dépendances, on vérifie qu'elles forment bien un DAG. C'est précisément le sujet de l'article suivant.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 22.3 (coloration et classification des arêtes) et 22.4. MIT Press.
• Tarjan, R. E. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2).
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 4.2 "Directed Graphs". Addison-Wesley.