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 java :

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
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.

Merci BEAUCOUP !!!

[tbc92]

Vu de loin, en regardant les commentaires, le principe me semble bon.

Pour ce genre de problème, je déclare une structure
str est composé de
tbs est un tableau de sommets
marque est un tableau de booleens
fin

Et dans ma pile, je vais empiler/dépiler ces structures.

Ici, j'ai l'impression que tu empiles une structure, et ensuite, tu modifies ton tableau marque[] ... mais ton tableau marque[] ne fait pas partie de la structure que tu empiles/dépiles.

Mais je ne comprends pas le Javanais ; peut-être que je me trompe en lisant le code.
Tu auras peut-être plus de réponses en postant sur le forum Java.