Salut !

Question pour pouvoir te répondre. Un circuit, c'est une boucle ? (genre celle que te donne le lemme de l'étoile si tu connais) ? Et un niveau, ca correspond à quoi ? Parce que j'en ai fait un peu de l'algorithmie, mais là j'vois pas...

Si t'as ces réponses, j'veux bien essayer de voir...

WS

Bonjour sana92!

Pour voir si ton graphe est avec ou sans circuit, tu peux faire un parcours dans le graphe en marquant les sommets visités. Mais le mieux est de remarquer qu'un graphe sans circuit a au moins un sommet sans prédécésseur et au moins un sommet sans succésseur.

On peut partir du principe que le graphe est sans circuit et essayer de trouver un tri topologique. Si on trouve ce tri c'est que le graphe est sans circuit. Si on trouve à un moment donné un ensemble de sommets ayants tous des prédécésseurs on peut être sûrs qu'il existe un cycle. Voici le principe du tri topologique:

On part d'un sommet sans prédécésseur et on l'appelle 1. On enlève ce sommet du graphe (et ses arcs adjacents) et on recommence: on choisit un sommet sans prédécésseur, on l'appelle 2 et on l'enlève du graphe. Et ainsi de suite. Si on arrive à numéroter de cette façon tous les sommets c'est qu'il n'y a pas de cycle. Parcontre si au cours de cet algo on a un ensemble non vide de sommets, dont aucun est sans prédécésseur, c'est que le graphe a au moins un cycle.

Isis