J'ai écrit un algorithme en CaML, qui était censé me renvoyer, étant donné un graphe non orienté g et un sommet initial k, la liste de tous les chemins possibles de longueur 4. C'est bien ce qu'il fait, mais il me les renvoie chacun en plusieurs fois (plus précisément, il en renvoie autant que le degré du dernier sommet visité. Par exemple, si le degré de 6 vaut 4, il renvoie en 4 fois le chemin [1;2;3;6]). Je précise que je prends un graphe du type (int vect) vect.
Voici mon code :
Code : Tout sélectionner
let whoop g k=
let h = ref [] in
let rec wop g k j l = match j with
| 3 -> h := (rev l)::(!h)
| _ -> let n = vect_length g.(k - 1) in
for i = 0 to (n - 1) do
wop g g.(k - 1).(i) (j + 1) (k :: l)
done;
in wop g k 0 [];
!h ;;
j'ai une liste référence h dans laquelle je vais stocker tous les chemins.
la fonction récursive wop prend 4 arguments : le graphe g, le sommet initial k, le nombre de sommets parcourus j, et enfin une liste dans laquelle on stocke le chemin en train d'être parcouru l.
A partir de la, je distingue le cas j<4 et le cas j=4, car je veux des chemins de longueur 4.
Si j=4, je mets la liste l dans h (en la renversant pour avoir le chemin dans le bon ordre).
Sinon, j est inférieur à 4 et alors je relance ma fonction récursive wop, en la faisant partir d'un des sommets adjacents au sommet k sur lequel on se trouvait, et en ajoutant k à la liste courante. Enfin, j'ajoute aussi 1 à j.
Enfin, les indices (k-1) (et pas k), viennent du fait que je souhaite afficher mes sommets en partant de 1 et pas de 0.
En fait, je vois d'où vient le problème: c'est quand j vaut 3, je relance ma fonction autant de fois que la valeur du degré du dernier sommet visité. Puis j vaut 4 et donc ça me les affiche en plusieurs exemplaires. Mais je n'arrive pas à modifier le code de sorte à résoudre tout ça.
Merci !