Discussion :

[Koelite]

Bonsoir,

J'ai un graphe G(V, E) non cyclique défini par une matrice d'adjacence M telle que pour tout i, j dans V², M[i][j] = 1 s'il y a un arc de i vers j et 0 sinon.

Est-il possible de parcourir tous les chemins élémentaires de ce graphe ?
Vous trouverez un exemple en pièce jointe.

Je remercie par avance tous ceux qui auront pris le temps de lire ou de répondre à ce post.

Bonne soirée.

PS : je code en C.

[dourouc05]

Oui, c'est tout à fait possible : en fait, c'est une question d'interview technique assez courante, que tu peux aborder avec une exploration en largeur du graphe, BFS (ça devient plus compliqué à gérer dès que tu peux avoir des boucles). Je pense qu'une exploration en profondeur (DFS) pourrait aussi marcher. En tout cas, les deux approches sont indépendantes de la représentation du graphe.

[Galet]

Bonjour,
Voici ce que j'avais trouvé de mieux dans mes recherche, pour traiter les généralités des graphes. Tu devrais trouver ton bonheur au chapitre III-3.

Perso, je serais plutôt allé du côté de la lecture en profondeur, en verrouillant le recursif dès qu'un nœud est antérieur à celui traité (même si tu précises que ton graphe n'a pas de cycle).
Cordialement,

[tbc92]

Je pense que la première étape, ce serait de clarifier la question.
Parcourir un graphe comme celui sur le dessin, ça veut dire quoi ?

A priori, on a un point de départ, et une fois qu'on a choisi ce point de départ, on recense tous les parcours possibles.
Par exemple, si le point de départ est le point 2, le programme devra afficher :
2-3-5
2-3-6
2-4-6
2-4-7
Et si le point de départ est 3, il devra afficher
3-5
3-6
Est-ce bien ça l'objectif ? Je suppose, mais je n'en suis pas sûr.

Quand on sait d'où on part ( le graphe), quand on connaît l'objectif, on peut chercher.
Si on n'a pas défini clairement l'objectif, c'est mort.

[Flodelarab]

Bonjour

ça devient plus compliqué à gérer dès que tu peux avoir des boucles

Ben justement. Le mot important est "élémentaire". Sans cycle. Donc bon. L'exercice consiste à chercher les cycles. N'est-ce pas ?