Modélisation réseau villes (java) Fermé

Question

Bonjour à tous,  
j'ai un petit problème avec mon tp d'info sur les graphes en java. 
Je dois modéliser un réseau de villes suivant cette représentation (voir lien) 

http://img38.imageshack.us/img38/9131/schemareseau.png 

On doit écrire une fonction qui partant d'une ville choisie nous donne tous les chemins possible 
Notre prof nous a donné le code ci dessous.  

public class Routes {  

 static int[][] tab={   
  {1,2},  
  {3,4},  
  {5,6},  
  {7},  
  {7},  
  {8},  
  {8},  
  {},  
  {}  
 };  
 static void parcours(int[]debChe,int arr){  
  int ext=extremite(debChe);  
  int indExt=extremite2(debChe);  
  if (ext==arr){  
   afficher(debChe);  
  } else {  
   if (tab[ext]!=null){  

    for (int i=0;i<tab[ext].length;i++){  
     int sauv=indExt;  
     indExt++;  
     debChe[indExt]=tab[ext][i];  
     afficher(debChe);  
     parcours(debChe,arr);  
     debChe[indExt]=-1;  
     indExt=sauv;  

    }  
   }  
  }  
 }  
 static int extremite(int[] ch){  
  int i=0;  
  while (ch[i]!=-1 && i<ch.length-1){  
   i++;  
  }  
  return ch[i-1];  
 }  
 static int extremite2(int[] ch) {  
  int i=0;  
  while (ch[i]!=-1 && i<ch.length-1){  
   i++;  
  }  
  return i-1;  
 }    
 public static void main(String[]args) {  
  int[] t={0,-1,-1,-1,-1,-1,-1,-1,-1};   
  parcours(t,8);  
 } 
 static void afficher(int[] t) {  
  int i=0;  
  while (t[i]!=-1 && i<t.length){  
   System.out.print(t[i]+" - ");  
   i++;  
  }  
  System.out.println();  
 }  

}  

Résultat: 
0 - 1 -  
0 - 1 - 3 -  
0 - 1 - 3 - 7 -  
0 - 1 - 4 -  
0 - 1 - 4 - 7 -  
0 - 2 -  
0 - 2 - 5 -  
0 - 2 - 5 - 8 -  
0 - 2 - 5 - 8 -  
0 - 2 - 6 -  
0 - 2 - 6 - 8 -  
0 - 2 - 6 - 8 -  



L'ennui c'est qu'elle marche pour la ville 0 mais je ne vois pas comment cet algo fonctionne (ouai j'avoue moi niveau est pas terrible)et du coup je sais pas comment afficher tous les chemins possible à partir d'une autre ville. 
Merci de bien vouloir m'aider 


Configuration: Mac OS X / Safari 533.21.1

mamiemando · Answer

Bah disons que c'est (désolé pour ton prof) codé n'importe comment (noms de variables douteux (genre debChe pour debutChemin), code non commenté et structure de données utilisée pour stocker le graphe discutable, ça aurait été un peu plus stylé de faire une class Graph... qui existe peut être même déjà en Java :p).  

Au passage merci d'utiliser les balises de code (bouton <> quand tu écris un message).  

En gros ton prof code le graphe dans la variable tab. La valeur tab[i] donne l'ensemble des sommets adjacents à i. Vu la manière dont c'est codé, les arcs sont stockés de manière mono-directionnelles ce qui explique pourquoi ton algorithme ne marche pas en partant d'un autre sommet que 0.  

Ainsi il faudrait ajouter les liens manquants dans tab :  

static int[][] tab={  
  {1, 2},  
  {0, 3, 4},  
  {0, 5, 6},  
  {1, 7},  
  {1, 7},  
  {2, 8},  
  {2, 8},  
  {3, 4},  
  {5, 6}  
}; 

Bonne chance

Modélisation réseau villes (java)

1 réponse

Discussions similaires