detection d'impasse dans un graphe

Bonjour,

Voila je suis sur la realisation d'un simulateur de fourmiliére en graphe, toute la structure est monté, un algo simpliste parcours le graphe jusqu'a trouver la sortie mais seule probleme, mes fourmis sont pas capables de detecter une impasse donc si par malheur elle y sont elle y reste! pas top!
je voudrai verifier mon graphe avant pour determiner les sommets à eviter, on connait l'entrée et la sortie il me faut analyser le graphe et repertorié le chemin à eviter dans un tableau d'entier,
seulement je ne voit pas comment faire, j'avais penser a un parcours en profondeur, mais comment detecter les sommets à eviter??

merci de votre aide

Qu'appelles-tu une impasse?
Ton graphe est orienté?

les fourmis ne font que avancer elles ne reculents jamais, nous pouvons donc considerer le graphe comme oriente j'apelle impasse un sommet different du sommet sortie et dont les somemt ajdacent ont deja etait tous vistes.

Citation:

---

Envoyé par aimad41

Voila je suis sur la realisation d'un simulateur de fourmiliére en graphe, toute la structure est monté, un algo simpliste parcours le graphe jusqu'a trouver la sortie mais seule probleme, mes fourmis sont pas capables de detecter une impasse donc si par malheur elle y sont elle y reste! pas top!
je voudrai verifier mon graphe avant pour determiner les sommets à eviter, on connait l'entrée et la sortie il me faut analyser le graphe et repertorié le chemin à eviter dans un tableau d'entier,
seulement je ne voit pas comment faire, j'avais penser a un parcours en profondeur, mais comment detecter les sommets à eviter??

---

Aucun rapport avec le langage C. Le bon forum est 'Algorithmes' :

http://www.developpez.net/forums/forumdisplay.php?f=60