Discussion :

[Drakkenator]

Bonsoir,

Dans le cadre d'un petit projet Java j'ai à déterminer à partir d'une matrice binaire si un circuit est présent ou non.

En l’occurrence si je me retrouve avec une matrice de ce type, visuellement il n'y a pas de problème :

- A B C D E
A 0 1 0 1 0
B 1 0 1 0 1
C 0 1 0 0 0
D 1 0 0 0 1
E 0 1 0 1 0

ou plus simplement :

- A B C D E
A 0 1 0 1 0
B X 0 1 0 1
C X X 0 0 0
D X X X 0 1
E X X X X 0

A -> B -> E -> D -> A

Mais d'un point de vue algorithmique et plus précisément en Java avez-vous des idées ? Je pensais avec un parcours en profondeur mais je me demande si c'est le mieux..

Donc quelles sont les solutions selon vous pour déterminer si un circuit est présent dans une matrice de graphe ?

Merci d'avance

[dinobogan]

Le parcours en profondeur permet de trouver facilement les composantes connexes. Pour les cycles, il va falloir creuser un peu plus. Quelles sont les contraintes ? Dois-tu trouver un cycle quelconque ? Possèdes-tu le nœud de départ ?

[professeur shadoko]

j'ai l'intuition qu'un algo rigolo à base de manipulation de matrices d'entiers peut le faire .....