Recherche d'un cycle dans un graphe par récurrence

Bonjour,
je n'arrive pas à créer un algorithme permettant de résoudre mon problème. J'ai pensé à une fonction récursive mais je n'y arrive pas. Voici mon problème :
Je possède un fichier (environ 100000 lignes) de la forme suivante
1 : 2
1 : 3
1 : 4
2 : 6
2 : 7
4 : 6
4 : 7
6 : 1
6 : 7
7 : 2
8 : 1

Ce fichier peut aussi être écrit comme cela :
1 : (2,3,4)
2 : (6,7)
4 : (6,7)
6 : (1,8)
7 : (2)
8 : (1)

Ce que je veux faire, c'est trouver tous les cycles possibles. Par exemple :
1 -> 2 -> 6 -> 1
1 -> 4 -> 6 -> 1
2 -> 7 -> 2
6 -> 8 ->1 -> 2 -> 6.
Les chemins suivants sont à ignorer :
1 -> 3 qui n'existe pas : on s’arrête.
Si un chemin ne donne pas de cycle il doit être ignoré.

Pour chaque valeur, j'ai une liste de 0 à 10 éléments.
Si quelqu'un peut me donner une idée...
Merci

Pour commencer, je suppose que la deuxième ligne 6 est "6 : 8", vu les cycles que tu donnes ensuite.

En fait, ton problème est une recherche de cycles dans un graphe orienté, chaque ligne correspondant à un arc dans ton graphe.

Il y a une discussion là dessus ici : http://www.developpez.net/forums/d10...cles-d-graphe/

Et tu as des algorithmes ici : http://en.wikipedia.org/wiki/Cycle_detection

Citation:

---

Envoyé par 10_GOTO_10

Et tu as des algorithmes ici : http://en.wikipedia.org/wiki/Cycle_detection

---

Merci, je viens de regarder cette page mais est-ce qu'elle s'applique à mon cas ? Moi je n'ai pas forcément une 'fonction'.
En effet, le 1 par exemple peut donner 2, 3 ou 4. C'est ça que je n'arrive pas à écrire récursivement.
Olivier

Citation:

---

Envoyé par olivier_1970

Merci, je viens de regarder cette page mais est-ce qu'elle s'applique à mon cas ? Moi je n'ai pas forcément une 'fonction'.
En effet, le 1 par exemple peut donner 2, 3 ou 4. C'est ça que je n'arrive pas à écrire récursivement.
Olivier

---

Pour pouvoir t'aider précisément, nous avons besoin d'en connaitre plus sur ta méthode actuelle.
Utilises-tu une matrice d'adjacences ? Un tableau global avec les valeurs envisagées successives ?
Tes données sont de grande taille, n'emploie pas un tableau local à la récursion pour éviter un dépassement de mémoire.

Sinon, la fonction de récursion devrait fort ressembler à cela

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

MaFonction (premierElementDeLaPile,tableauDAdjacences) si l'élément est égal au premier élément de la pile globale, {imprimer la liste}   sinon { générer les éléments adjacents à l'élément courant de la pile (tous les j | T[élémentCourant][j]==1] { ajouter l'élément généré à la pile appel de MaFonction(premierElementDeLaPile,tableauDAdjacences) dépiler l'élément courant de la pile } }

---

Bon courage!