Discussion :

[marc_dd]

Bonjour à tous ,
Voilà j ai un probléme d'algorithme, je fais une application qui travaille sur des graphes, j'ai tout sauf le moyen pour arriver à trouver les circuits dans une matrice booléenne, j'ai déjà essayer plusieurs choses mais rien ne marche
C'est sur des graphes orientés
Quelqu'un pourrait-il m'éclairer??

D'avance merci
Marc

[progfou]

Qu'as tu essayé comme algorithmes ?
Tu travailles avec les listes ou les matrices ?

[roulious]

Que fais-tu dans le cas d'un graphe ayant 3 somments a,b et c avec des arêtes a->b, b->c et c->a ?

Puisque tu travailles sur un graphe orienté, un parcours en profondeur peut servir : si tu retombes sur un sommet déjà parcouru, tu as un circuit.

[marc_dd]

en premier lieu je travil avec des matrice

et j ai essayer ce que tu a dis masi je n arrive pas je travail avec un parcour en profondeur comme tu me le propose mais je ne trouve pas
Ca fait aussi toute la journée que je suis la dessus je n' ai donc peut être plus les idées très claire

merci de votre aide
Marc

[millie]

Les matrices sont-ils imposées ?

Car il me semble que réaliser des parcours en profondeur sur une matrice est beaucoup plus lent qu'avec une liste (de successeur par exemple).

Car pour obtenir l'ensemble des successeurs d'un sommet (utile pour le parcours), on passe d'une complexité constante (ou à peu près) à une complexité = nombre de sommets.

[millie]

Si ça t'interesse, j'avais répondu à qqn qui voulait réaliser un parcours en profondeur ici :

http://www.developpez.net/forums/sho...ghlight=graphe

[marc_dd]

Ce n 'est pas que c'est imposé mais c 'est que j' ai deja fait tout mon programme comme ca, je fait un parcour en profondeur pour le chemin et la ca marche mais avec les circuits je ne sais pas j'arrive pas à trouver la solution
j'utilise aussi un parcours en profondeur mais y a un bug
Faut dire aussi que ca fait depuis hier que je suis sur les 2 même méthodes je n 'y vois plus très clair

Merci de votre aide
Marc