problème pour trouver un circuit dans une martice booleenne

Question

Bonjour à tous,
Pour mon cours de math je dois faire une application sur des graphes, j'ai presque fini mais il me reste un problème je cherche un algorithme me permettant d'afficher tous les  circuits qui se trouvent dans le graphe à partir de sa matrice booléenne. 
J'ai cherché sur le net mais je n'ai pas trouvé, j'ai déja essayé plusieurs choses mais ca ne marche pas 
Quelqu'un pourrait-il m'aider

merci d'avance
Marc

cs_DARKSIDIOUS · Answer

Je présume que ta matrice représente les arêtes de ton graphes : un 1 si tu peux aller du sommet (colonne de ta matrice) jusqu'au sommet (ligne de ta matrice).

Fait une fonction récursive qui part d'un sommet et qui avance d'un sommet à chaque appel par exemple.

marc_dd · Answer

C'est ce que j ai éssayé de faire mais j'arrive pas  je dois faire une rreur , pourtant j'ai déjà réussi la fonction qui cherche les chemin 

merci d'avance
Marc

cs_DARKSIDIOUS · Answer

Passe nous ton bout de code en nous disant ce qui ne marche pas et nous le corrigerons.

marc_dd · Answer

Voilà mes 2 methode, je dois surement m'être embrouiller pas mal ca fait toute la journée que je suis sur les chemins et les circuits

1ere methode 
 public int Circuit ()
 {
  tmpcirc = new String [100];
 
  arcirc = new ArrayList();
  int n = 0;
  Demarqué();
  for (int a=0;a<count;a++)
  { 
   if(matbool[0][a]==1 && a!=0)
          n+=profcirc(0,a);
         Demarqué();
         arcirc.add(lignecircuit);
         initcirctmp();
         lignecircuit="";
  }
  Iterator it = arcirc.iterator();
  while (it.hasNext())
  {
         String li = (String)it.next();
         System.out.println(li+"
");
  }
  
  return n;               //nombre de chemin qu'il y a
 }

2eme methode  (la recursive)

public int profcirc(int l, int c)
 {
  int n=0;
  int ind=0;
  ind = chindice();
  tmpcirc[n]= tabsommet[l].getNom();
  tabsommet[l].setP(true);
  for (int a=0;a<count;a++)
  {
   if (matbool[c][a]==1 )
   {
    if (tabsommet[a].getP() && tabsommet[a].getNom()!=tmpcirc[n])
     {
     int inttmp= chindice();
     tmpcirc[inttmp]=tabsommet[a].getNom()+" ";
     int indicech=0 ;
     for (int i=inttmp;i>=0;i--)
     { if ( tmpcirc[i]==tmpcirc[inttmp])
                  indicech=i;
     }
     for (int i=indicech;i<=inttmp;i++)
      lignecircuit+=tmpcirc[i]+" ";
        return n=1;
     }
     else if (c!=a) profcirc(c,a);  
   }
  }
  return n;
 }

voilà 
merci d'avance pour votre aide 

merci d'avance
Marc

marc_dd · Answer

bonjour à tous , 


j'ai réessayer un autre algorithme avec un arrylist temporaire mais marche toujours pas oilà mon code ;


 
public int Circuit ()
 {
  tmpcirc = new String [100];
 artmp = new ArrayList();
  arcirc = new ArrayList();
  int n = 0;
  Demarqué();
  for (int a=0;a<count;a++)
  { 
   if(matbool[0][a]==1 )
    n+=profcirc(0,a);
   Demarqué();
  // if (lignecircuit!="")
   //arcirc.add(lignecircuit);
   initcirctmp();
   lignecircuit="";
  }
  Iterator it = arcirc.iterator();
  while (it.hasNext())
  {
   String li = (String)it.next();
   System.out.println(li+"
");
  }
  
  return n;
 }
 public int profcirc(int l, int c)
 {
  int n=0,k=0;
  int ind=0;
  ind = chindice();Iterator it ;
  
  artmp.add( tabsommet[l].getNom());
  tabsommet[l].setP(true);
  for (int a=0;a<count;a++)
  {
   if (matbool[c][a]==1)
   {it = artmp.iterator();
    while (it.hasNext())
    {
     n++;
    }
    if (artmp.indexOf(tabsommet[a].getNom())==n-1)
     ;
    else if (artmp.contains(tabsommet[a].getNom()))
    {
     int nb = artmp.indexOf(tabsommet[a].getNom());
     it = artmp.iterator();
     n=0;
     while (it.hasNext()){
      if (n>=nb){
       lignecircuit+=it.next()+" ";
       
       lignecircuit="";}
      else n++;
     }arcirc.add(lignecircuit);
     return k=1;
    }
    else{ 
    profcirc(c,a);
    }
   }
   
  }return k;
   
Merci de votre aide

Marc

Problème pour trouver un circuit dans une martice booleenne

5 réponses

Votre réponse

Discussions similaires