recherche tous les chemins dans un graphe orienté

[invitea5e67aa9]

Bonjour,

j'ai un graphe orienté que j'ai défini en c de la façon suivante:

#include "stdio.h"
#include "stdlib.h"

typedef struct
{

int num;

int ListeSuiv[3];
int ListePrec[3];

}Point_Graph;


Point_Graph P0;
P0.num=0;
P0.ListeSuiv[0]=1;
P0.ListeSuiv[1]=2;
P0.ListeSuiv[2]=3;


Point_Graph P1;
P1.ListeSuiv[0]=4;
P1.ListeSuiv[1]=5;
P1.ListePrec[0]=0;

Point_Graph P2;
P2.num=2;
P2.ListeSuiv[0]=4;
P2.ListeSuiv[1]=5;
P2.ListeSuiv[2]=6;
P2.ListePrec[0]=0;

Point_Graph P3;
P3.num=3;
P3.ListeSuiv[0]=5;
P3.ListeSuiv[1]=6;
P3.ListePrec[0]=0;

Point_Graph P4;
P4.num=4;
P4.ListeSuiv[0]=7;
P4.ListeSuiv[1]=8;
P4.ListePrec[0]=1;
P4.ListePrec[1]=2;

Point_Graph P5;
P5.num=5;
P5.ListeSuiv[0]=7;
P5.ListeSuiv[1]=8;
P5.ListeSuiv[2]=9;
P5.ListePrec[0]=1;
P5.ListePrec[1]=2;
P5.ListePrec[2]=3;


Point_Graph P6;
P6.num=6;
P6.ListeSuiv[0]=8;
P6.ListeSuiv[1]=9;
P6.ListePrec[0]=2;
P6.ListePrec[1]=3;

Point_Graph P7;
P7.num=7;
P7.ListeSuiv[0]=10;
P7.ListePrec[0]=4;
P7.ListePrec[1]=5;

Point_Graph P8;
P8.num=8;
P8.ListeSuiv[0]=10;
P8.ListePrec[0]=4;
P8.ListePrec[1]=5;
P8.ListePrec[2]=6;

Point_Graph P9;
P9.num=9;
P9.ListeSuiv[0]=10;
P9.ListePrec[0]=5;
P9.ListePrec[1]=6;


Point_Graph P10;
P10.num=10;
P10.ListePrec[0]=7;
P10.ListePrec[1]=8;
P10.ListePrec[2]=9;


telle que P0, ..., P10 sont numérotés de 0 à 10 avec ListeSuiv les points suivants et ListePrec les points qui précèdent.

Je souhaite déterminer le nombre d'itinéraires possibles qui vont de P0 à P10.

Merci de votre aide!
-----

[invitebe0cd90e]

Salut,

Ca n'etait pas forcement necessaire de nous donner ton grapge explicitement

D'une façon générale, pour trouver ça il suffit de faire un bete parcours en profondeur avec un algorithme récursif. La seule chose c'est qu'il faut éviter les eventuelles boucles sinon l'algorithme ne terminera pas. Pour ca, ajoute à ta structure de sommet une variable booléenne, appellons la "dejaVisite", mise a 0 par defaut. Ensuite :

tu parcours recursivement ton graphe en partant du point de depart
a chaque fois que tu tombes sur un sommet
- si dejaVisite est 0, tu mets dejaVisite a 1 (y compris pour le point de depart !) et tu continues
- si dejaVisitee est a 1 tu t'arretes
si tu tombes sur le sommet d'arrivée, tu incrementes la variable qui compte le nombre de chemin.

Attention quand tu remontes dans ta recursion a bien remettre dejaVisite a 0 pour le chemin suivant.

Il me semble que ca devrait te donner ce que tu veux.