Chercher des chemins et détecter des cycles

Préciser le sens d’un chemin

Un chemin est une succession de sommets reliés conformément aux liaisons du graphe. Dans un graphe orienté, chaque arc doit être suivi dans son sens. A→B n’autorise pas automatiquement B→A. L’accessibilité dépend donc du point de départ et n’est pas nécessairement réciproque.

Pour fournir un témoin d’accessibilité, on donne un chemin concret. Pour montrer une impossibilité, on peut parcourir tous les sommets accessibles depuis le départ et constater que la destination n’en fait pas partie. Une exploration arrêtée trop tôt ne suffit pas à prouver l’absence de route.

Par convention, un sommet est accessible depuis lui-même par un chemin de longueur zéro. Cela ne prouve pas qu’il existe un cycle : aucun arc n’a été parcouru. Distinguez explicitement ce chemin vide en liaisons d’un trajet non vide qui revient à son départ.

Conserver le prédécesseur de découverte

Lorsqu’un parcours découvre v depuis u, on enregistre u comme prédécesseur de v. Une fois la destination trouvée, on remonte ces liens jusqu’au départ puis on inverse la liste. Cette technique évite de conserver à chaque instant toutes les routes possibles.

Si pred[D]=B et pred[B]=A, on reconstitue D,B,A puis A,B,D. Le départ doit posséder un marqueur d’arrêt, comme None. Une destination non découverte n’a pas de chaîne valide à remonter. Avec BFS dans un graphe non pondéré, le chemin ainsi reconstruit possède un minimum d’arêtes.

Détecter un cycle dans un graphe non orienté simple

Dans un graphe simple non orienté, parcourir l’arête A-B depuis A puis constater que B voit A ne suffit pas à déclarer un cycle : c’est la même arête examinée dans l’autre sens. Une recherche en profondeur doit distinguer le parent de découverte des autres voisins déjà visités.

Si l’on rencontre un voisin déjà découvert qui n’est pas le parent dans ce modèle, une liaison supplémentaire referme un trajet et révèle un cycle. Le graphe A-B, B-C forme une chaîne sans cycle ; ajouter C-A crée le cycle A-B-C-A. Les multigraphes ou les boucles exigent des conventions supplémentaires et ne sont pas supposés ici.

Dans un graphe orienté, suivre les sommets actifs

Pour un DFS orienté, il faut distinguer un sommet encore dans la pile des appels d’un sommet dont l’exploration est terminée. Un arc vers un ancêtre encore actif referme un cycle dirigé. Un arc vers un sommet terminé ne prouve pas nécessairement un cycle.

Le graphe A→B, A→C, C→B est sans cycle, bien que C puisse rencontrer B déjà visité. Ajouter B→A crée au contraire A→B→A. Une classification « inconnu, actif, terminé » permet de raisonner proprement. Comme souvent en algorithmique, mémoriser seulement un booléen peut être insuffisant lorsque la question demande une distinction plus fine.

Voici une détection complète pour un graphe orienté fini donné par listes de successeurs. Les états 1 et 2 représentent actif et terminé. La boucle extérieure traite aussi les zones qui ne sont pas accessibles depuis le premier sommet.

def a_un_cycle_oriente(graphe):
    etat = {sommet: 0 for sommet in graphe}
    def explorer(u):
        etat[u] = 1
        for v in graphe[u]:
            if etat[v] == 1:
                return True
            if etat[v] == 0 and explorer(v):
                return True
        etat[u] = 2
        return False
    for u in graphe:
        if etat[u] == 0 and explorer(u):
            return True
    return False

Exemple suivi : distinguer trois couleurs

Dans le graphe orienté A→B, A→C, C→B, commençons DFS en A et examinons B avant C. A devient actif, puis B devient actif. Comme B n’a aucun successeur, il termine. A explore ensuite C ; C rencontre B déjà terminé. Cet arc ne remonte pas vers un appel actif et ne crée aucun chemin de retour depuis B. Le graphe reste sans cycle.

Ajoutons maintenant B→A. Lorsque B examine A, celui-ci est encore actif : A attend justement le retour de B. Les arcs A→B et B→A forment un cycle dirigé. Un tableau à trois états, inconnu, actif, terminé, conserve l’information nécessaire. Un booléen « déjà vu » confondrait B terminé dans le premier scénario et A actif dans le second. La structure de mémoire dépend donc de la propriété recherchée.

Exemple suivi : une route inverse et un témoin local

Dans la chaîne non orientée A-B-C, les prédécesseurs depuis C sont B←C et A←B. La remontée depuis A donne A,B,C ; l’inversion fournit C,B,A. Le trajet utilise les arêtes dans le sens inverse de leur écriture initiale, ce qui est autorisé parce qu’elles ne sont pas orientées. Le dessin doit surligner les mêmes deux liaisons, quelle que soit la direction du trajet.

La présence d’un cycle est une propriété du graphe considéré, tandis qu’un chemin dépend aussi du départ et de la destination. Dans un graphe comportant plusieurs composantes, un cycle peut se trouver hors de la zone atteignable depuis le départ. Une détection globale doit alors relancer DFS sur les sommets encore inconnus. Pour prouver un chemin, une suite valide suffit ; pour prouver une absence, explorez tout ce qui est accessible ou utilisez une contrainte structurelle claire, comme l’absence de successeur au départ.

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

Déclarer un cycle pour tout voisin déjà visité.

Le parent en non orienté et les sommets terminés en orienté nécessitent des traitements distincts.

Remonter les prédécesseurs d’une destination inconnue.

Vérifiez d’abord que la destination a été découverte.

Cette notion au bac

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

• Bac 2025 · Métropole · Remplacement jour2 - 10 septembre 2025 : Commandes SQL et itinéraires de livraison
• Bac 2025 · Centres étrangers groupe 1 · Jour 2 : Diviseurs et multiples : énumérer les chemins sans répétition
• Bac 2025 · Nouvelle-Calédonie · Jour 2 : Jonglerie : construire puis parcourir un automate de siteswaps

Le prochain pas

• Les interblocages : comprendre et éviter un blocage mutuel
• Coûts en temps et en mémoire

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.