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

[Raikyn]

Non justement j'ai précisé sans cycles

[kija13]

Imagine un arbre (construit à partir de ton graphe)
la racine est le noeud de départ et les fils sont les noeuds voisins (pris dans un ordre fixé). Cet arbre est infini mais on le parcourt en profondeur avec comme test d'arrêt que le fils examiné est déjà dans la liste ; ainsi on est sûr que le parcours est fini.

Je ne sais pas dans quel langage tu codes donc en pseudo code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
List<Noeud> listeCourante = new List<Noeud>;
List<List<Noeud> > tousLesChemins = new List<List<Noeud> >;
Noeud leNoeudDeDepart;
leNoeudDeDepart.examiner(listeCourante, tousLesChemins);

avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
void Noeud::examiner(List<Noeud> liste, List<List<Noeud> > total)
{
    if( ! this.estDans( liste ))
    {
        List<Noeud> nouvelle = new List<Noeud>(liste); // recopie
        nouvelle.add(this);
        total.add(nouvelle);
        foreach fils in lesNoeudsVoisins
        {
            fils.examiner(nouvelle, total);
        }
    }
}

à la fin tous les chemins sont dans....tousLesChemins
il reste la liste vide du début à supprimer
je te laisse choisir au niveau du passage des paramètres

[Raikyn]

Merci beaucoup, je vais tester ça en java !

Edit : Je confirme que ça marche très bien en java, encore merci