Discussion :

[AP]

Bonjour à tous,

J'ai un digraphe (graphe orienté) que je représente par liste d'adjacence. Mon problème est de savoir comment faire pour vérifier que le graphe ne comporte pas de cycle.
J'ai essayé un algo de parcours en profondeur en marquant les sommets mais cela ne fonctionne pas.

Avez-vous d'autres idées? En effet si internet regorge d'exemples pour les graphes non orientés, je n'ai rien trouvé pour les graphes orientés.

Merci par avance

[MysticKhal_0]

Salut.

La méthode que tu as utilisé est la bonne.. Surment un problème au niveau du code..

[millie]

Une cause possible d'erreur :

Ce n'est pas un vrai parcours en profondeur qu'il faut réaliser au sens ou tu ne colores pas le sommet de départ, contrairement au classique parcours en profondeur. Car sinon à la fin, lorsque tu regarderas ton ensemble de sommets visités, le sommet de départ y sera forcement donc on pourrait penser qu'il y a un cycle.

[AP]

Merci pour vos réponses.
Je veux bien qu'il y ait une erreur dans mon code mais j'aimerais juste savoir comment vous gérez le cas suivant:

A->B;
A->C;
C-> D
B->D ?

en effet si l'on part de A, on passera 2 fois par D (alors qu'il n'y a pas de cricuit dans ce graphe)

[millie]

On réalise un parcours comme j'ai dit sur tous les sommets.

A->B;
A->C;
C-> D
B->D

On part de A.

On met sur la pile des AVISITER les successeurs de A, c'est à dire B et C.
On met sur la pile des VISITER rien du tout (contraitement au parcours classique)

Reste à visiter : B, C
On visite B
On met sur la pile des AVISITER les successeurs de B, c'est à dire D.
On met sur la pile des VISITER B


Reste à visiter : C, D
On visite C
On met sur la pile des AVISITER les successeurs de C, c'est à dire D.
On met sur la pile des VISITER C

Reste à visiter : D, D
On visite D
On met sur la pile des AVISITER rien du tout
On met sur la pile des VISITER D

Reste à visiter : D
On a déjà visiter.

Fini pour A

On vérifie, A n'appartient pas à la pile des VISITER, il n'y a pas de circuit passant par A.

Pis ainsi de suite.

On peut noter qu'on est pas obligé de parcourir tout en profondeur, on peut s'arrêter dès que A est un successeur d'un élément de la pile des AVISITER.


PS : J'ai parlé de pile, en général, quand on implémente, on utilise un tableau coloré ce qui est plus rapide !!! Mais pour l'explication, je preferai prd une pile.