Discussion :

[Raikyn]

Bonjour,

Je suis à la recherche d'un algorithme qui donne tout les chemins possible d'un graphe à partir d'un certain sommet.
Si possible qu'il soit adapté à ma structure de graphe qui est représenté tel que chaque sommet a une liste de ses voisins et un identifiant unique.


Merci d'avance pour votre aide !

[kija13]

Bonjour,
Si tu ne donnes pas de contraintes il y en a une infinité...
On fait une récursion mais il faut un test pour l'arrêt ( longueur ou arrivée sur un nœud donné ou autre)

[Raikyn]

Arf oui c'est vrai. Et bien sans cycle et il faut parcourir tout les nœuds.

J'avais dans l'idée d'utiliser le parcours en profondeur, c'est-à-dire de parcourir un chemin jusqu'au dernier nœud non visité, de revenir à l'avant dernier noeud pour regarder si il a d'autre voisins non visité puis revenir encore en arrière etc...
Je vois bien ce qu'il faut faire mais j'ai du mal à l'écrire correctement (encore moins à le programmer)

[kija13]

Il faut préciser encore ton type de graphe pour qu'on prenne la solution la mieux adaptée.
Est-ce un arbre?
Est-il orienté?
Peut-on joindre deux nœuds par deux chemins différents?

[Raikyn]

Mon type graphe est représenté par un sommet et une liste des voisins de ce sommet. Il est non orienté et il y a plusieurs chemins d'un sommet à l'autre.

En fait c'est une grille de lettre, et je dois trouver tout les mots possibles en prenant les lettres adjacentes (chaque lettre a plusieurs voisins, de 5 à 8).

[kija13]

Heu...si il n'est pas orienté et qu'il y a plusieurs chemins d'un nœud à l'autre il va y avoir des cycles et donc une infinité de chemins...
On tourne en rond, je pense que tu devrais reposer ton problème de façon plus
précise