Circuits et cycles
Les graphes orientés
On parle de circuits pour les graphes orientés
Exemple de graphe orienté avec circuit
Exemple de graphe orienté sans circuit
Les graphes non orientés
On parle de cycles pour les graphes non orientés
Exemple de graphe non orienté avec cycle
Exemple de graphe non orienté sans cycle
graphes acycliques
- Un graphe non orienté acyclique est un graphe qui ne contient pas de cycle.
- Un graphe orienté acyclique est un graphe qui ne contient pas de circuit.
Premiers essais
Nous nous plaçons dans le cas d'un graphe connexe.
Nous désirons savoir si ce graphe contient au moins un cycle, ou un circuit.
L'idée est la suivante : on parcourt le graphe en profondeur (on avance le plus loins possible vers la profondeur) à partir d'un sommet choisi arbitrairement. A chaque fois que l'on rajoute un sommet à notre parcours, nous regardons ses voisins. Si parmi ses voisins il y a
un sommet que l'on a déjà parcouru, c'est que le parcours se referme, il existe donc un cycle. Si on a terminé le parcours
du graphe sans jamais avoir été dans cette situation, on en déduit que le graphe ne contient pas de cycle.
graphe_1 :
graphe_2 :
graph LR
A --> BNous reprenons donc l'algorithme du parcours en profondeur itératif, auquel on a ajouté les lignes 12 et 13 pour détecter l'existence d'un cycle ou d'un circuit.
Que s'est-il passé?
Lorsque l'on parcourt graphe_1 en partant de "A", on parcourt "A", puis on arrive en "B". "A" fait partie des voisins de "B"
et donc un cycle est détecté. Par contre, dans graphe_2, "A" ne fait pas partie des voisins de "B", et il n'y a pas de cycle détecté
à ce stade.
graphe_1 aurait pu être représenté ainsi si on le considérait comme un graphe orienté :
graph LR
A --> B
B --> AGraphe orienté ou pas?
Nous constatons donc que l'algorithme doit être différent suivant que l'on travaille sur un cycle orienté ou pas.
Ici le graphe est non orienté, aucun cycle ne doit être détecté
Ici le graphe est orienté, un circuit doit être détecté
graph LR
A --> B
B --> A
B --> CCas des graphes non orientés
👉 Nous allons nous limiter à la recherche de présence de cycle dans un graphe non orienté connexe1.
Comment détecter la présence d'un cycle dans un graphe non orienté
Reprenons l'exemple de graphe_1
graphe_1 :
Nous parcourons ce graphe en profondeur en partant de A. Lorsqu'on arrive en B, on découvre A comme voisin, mais le graphe n'étant pas
orienté, il ne faut pas considérer ce nouveau voisin qui est le résultat de l'arc de retour.
Il suffit donc de reconnaître que A est le prédécesseur de B, pour ne pas considérer que A - B - A est un cycle.
👉 Comme nous avons déjà dû le faire pour la recherche de plus court chemin, nous allons donc construire le dictionnaire des prédécesseurs de chaque sommet.
Nous nous plaçons dans le cas d'un graphe non orienté connexe. On parcourt le graphe à partir d'un sommet choisi arbitrairement. A chaque fois que l'on rajoute un sommet à notre parcours, nous regardons ses voisins. Si parmi ses voisins il y a un sommet que l'on a déjà parcouru, et qui évidemment n'est pas celui dont on vient, c'est qu'il existe un cycle. Si on a terminé le parcours du graphe sans jamais avoir été dans cette situation, on en déduit que le graphe ne contient pas de cycle.
L'algorithme
Nous utilisons un parcours en profondeur. Au fur et à mesure de la progression, nous construisons le dictionnaire predecesseurs, qui prend pour clés les sommets visités, et pour valeur associée à chaque clé, le sommet d'où l'on vient. On arrete le parcours, et renvoie True si le voisin d'un sommet a déjà été parcouru, et si ce n'est pas celui d'où l'on vient.
Si le parcours entier a été effectué, la fonction renvoie False
Il n'est pas nécessaire de conserver la liste des sommets parcourus, comme nous l'avions fait dans le parcours en profondeur.
Nous allons utiliser le parcours en profondeur itératif.
À vous de jouer
Compléter le script ci-dessous
Les graphes utilisés pour les tests sont :
graphe_5 :
graphe_6 :
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Crédits⚓︎
Romain Janvier, Nicolas Revéret
-
Voir : Les graphes - Structure au paragraphe 1.2.4 : Structures de graphes ↩
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)