Problème pour trouver un circuit dans une martice booleenne

Messages postés
61
Date d'inscription
dimanche 30 octobre 2005
Statut
Membre
Dernière intervention
2 juillet 2009
-
Messages postés
61
Date d'inscription
dimanche 30 octobre 2005
Statut
Membre
Dernière intervention
2 juillet 2009
-
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

5 réponses

Messages postés
15814
Date d'inscription
jeudi 8 août 2002
Statut
Modérateur
Dernière intervention
4 mars 2013
133
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.
Messages postés
61
Date d'inscription
dimanche 30 octobre 2005
Statut
Membre
Dernière intervention
2 juillet 2009

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
Messages postés
15814
Date d'inscription
jeudi 8 août 2002
Statut
Modérateur
Dernière intervention
4 mars 2013
133
Passe nous ton bout de code en nous disant ce qui ne marche pas et nous le corrigerons.
Messages postés
61
Date d'inscription
dimanche 30 octobre 2005
Statut
Membre
Dernière intervention
2 juillet 2009

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+"\n");
  }
  
  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
Messages postés
61
Date d'inscription
dimanche 30 octobre 2005
Statut
Membre
Dernière intervention
2 juillet 2009

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+"\n");
  }
  
  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