Discussion :

[mhodier]

Bonjour à tous,


A force de me creuser la tête j'ai réussis à trouver une méthode me trouvant un chemin possible mais je n'arrive pas à me servir de la récursivité dans ma méthode pour tous les trouver. Car si mon sommet est marqué alors il n'y repasse pas alors que moi je ne veux pas qu'il repasse par un sommet déjà marqué dans un chemins mais dans les autres chemins, je veux qu'il puisse y retourner ! ^^

Voici mon code :

ma classe hérite d'une classe graphe où dans cette classe se trouve plusieurs méthode comme la liste des successeurs d'un sommet (réc ses prédécesseurs), le nombre de sommets etc.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
import java.util.*;
 
public class Cheminement extends Graphe{
 
//Vecteur dans lequel je stock mon chemin
private Vector<Integer> tab= new Vector<Integer>();
//tableau de boolean pour marquer un sommet et savoir s'il a déjà été visité
private boolean [] marque = new boolean[1000];
 
 
public void chemins(Graphe g, int depart, int arrivee){
int courant = depart;
for(int i=0; i<g.nbSommet(); i++){
marque[i] = false;
}
 
//Une pile P qui se rempli et se vide au fur et à mesure et permet de sortir de ma boucle while
Stack<Integer> P = new Stack<Integer>();
 
marque[depart] = true;
P.push(depart);
while(!(P.isEmpty())	&& courant!=arrivee){
courant = P.pop();
tab.add(courant);
for(int i=0; i<g.lst_succ(courant).length; i++){
if(marque[g.lst_succ(courant)[i]] == false){
P.push(g.lst_succ(courant)[i]);
marque[g.lst_succ(courant)[i]] = true;
}//fsi
}//fpour
}//fwhile
}//CheminHami
 
 
 
public java.lang.String toString(){
String str = "chemin : { ";
for(int i=0; i<tab.size(); i++){
str+= tab.get(i) + ", ";
}
str+="}";
 
return str;
}
 
 
public static void main(String[] args) {
Cheminement c1 = new Cheminement();
 
int A = Graphe.Alpha_NotDef; //Permet de dire qu'il n'y a pas d'arc entre les sommets
int [][]mat = {{A,2,2,A,A,A}, {A,A,A,A,2,A}, {A,2,A,2,A,A}, {A,A,A,A,A,2},{A,A,2,2,A,A}, {A,A,A,A,2,A}}; //Matrice d'adjacence de mon graphe g
Graphe g = new Graphe(mat); //Mon graphe g construit avec le constructeur par matrice
 
c1.chemins(g, 0, 5); 
System.out.println(c1);	
 
}
}

Pouriez-vous m'aider, sur mon code, à l'améliorer et me permettre de trouver tous les chemins possibles.


Si je ne nme trompe pas, avec ce graphe (donc avec cette matrice d'adjacence), tous les chemins possibles entre le sommet 0 et le sommet 5 sont :

0; 1; 4; 3; 5
0; 1; 4; 2; 3; 5
0; 2; 1; 4; 3; 5
0; 2; 3; 5


Parce que mon but final est de trouver tous les chemins possible reliant deux sommets passant par tous les sommets du graphe.
Mais ce but final je peux le chercher seul je pense pour ne pas trop vous en demander car je pense que si on m'aide à trouver tous les chemins possible entre deux point je serais capable de faire le deuxième objectif.

Merci BEAUCOUP !!!

[tbc92]

Utilise la balise Code (icone #) ça aide beaucoup pour lire le code.
Et précise ton besoin. Au début tu dis que tu veux recenser tous les chemins. Et à la fin, tu dis que tu veux recenser tous les chemins qui passent par tous les points. Ce petit détail supplémentaire est peut-être important si on veut un algorithme qui va vite.

[mhodier]

je viens de modifier pour la balise et j'ai également répondu à ta question de quel est réellement mon objectif à la fin mais je le redis :

Mon but final est de trouver tous les chemins possible reliant deux sommets passant par tous les sommets du graphe.
Mais ce but final je peux le chercher seul je pense pour ne pas trop vous en demander car je pense que si on m'aide à trouver tous les chemins possible entre deux point je serais capable de faire le deuxième objectif.