composante connexe

Question

Bonjour,

j'ai des noeuds reliés entre eux. et je veux savoir comment déterminer à partir de cet ensemble de lien les composantes connexes en JAVA.

merci.

cs_Julien39 · Answer

Salut,

Rien compris...

sassion · Answer

Salut,

j'ai un graphe constitué d'un ensemble de noeuds reliés entre aux par des arcs. je veux déterminer les composantes connexes dans ce graphe et de les afficher. je travail en java.

j'ai essayé mais j'ai pas la bonne solution.

Merci pour votre aide.

sassion · Answer

s'il vous plait essayer de m'aider je me bloque
Merci

sassion · Answer

voici le code. le problème est que il m'affiche les meme liens plusieurs fois?????


//Programme

package CC;
import java.io.IOException;
import java.util.*;
import java.applet.*;
import java.io.*;
import java.lang.*;

public class Conseiller {

public static void main(String[] args) throws IOException {
ArrayList tab = new ArrayList(100);
    Scanner sc=new Scanner(System.in);
    int C=1;
    tab.add(12);tab.add(26); tab.add(14);tab.add(28); tab.add(31);tab.add(22);
    tab.add(13);tab.add(26); tab.add(21);tab.add(13); tab.add(15);tab.add(28);
    tab.add(32);tab.add(15); tab.add(32);tab.add(14); tab.add(13);tab.add(28);
    tab.add(34);tab.add(16); tab.add(14);tab.add(27); tab.add(13);tab.add(24);
    tab.add(33);tab.add(25); tab.add(37);tab.add(28); tab.add(21);tab.add(17);
    tab.add(24);tab.add(35);

//Traitement	
int es=0;
ListIterator l=tab.listIterator();
boolean trouve = false;
//Object [] t =new Object[100];
ArrayList t1=new ArrayList();
ArrayList t=new ArrayList();
t.add(tab.get(0));
t.add(tab.get(1));
while(l.hasNext()){
es++;
int index=0;
Object rech=tab.get(0);
tab.remove(0);
ListIterator i=tab.listIterator();
while( i.hasNext()){
if((i.next()).equals(rech)){
int x=(i.previousIndex()-1);
int x2=(i.previousIndex()+1);
if(index % 2!=0 && es % 2!=0)
{
//t.add(tab.get(najla));
//t.add(rech);
t.add(rech);
t.add(tab.get(x2));
}
else{
if(index % 2!=0 || !i.hasNext()||es % 2!=0){
t.add(tab.get(x));
t.add(rech);
}
else{
t.add(rech);
t.add(tab.get(x2));
}
}
}
index++;
}
}

ListIterator k=t.listIterator();
           while(k.hasNext())
System.out.printf("
 le conseiller responsable de la contrainte X"+k.next()+" X"+k.next()+" est C"+C);
           C++;
           
}
}


//resultat

 le conseiller responsable de la contrainte X12 X26 est C1
 le conseiller responsable de la contrainte X13 X26 est C1
 le conseiller responsable de la contrainte X32 X14 est C1
 le conseiller responsable de la contrainte X14 X27 est C1
 le conseiller responsable de la contrainte X15 X28 est C1
 le conseiller responsable de la contrainte X13 X28 est C1
 le conseiller responsable de la contrainte X37 X28 est C1
 le conseiller responsable de la contrainte X21 X13 est C1
 le conseiller responsable de la contrainte X13 X28 est C1
 le conseiller responsable de la contrainte X13 X24 est C1
 le conseiller responsable de la contrainte X21 X17 est C1
 le conseiller responsable de la contrainte X13 X28 est C1
 le conseiller responsable de la contrainte X13 X24 est C1
 le conseiller responsable de la contrainte X32 X15 est C1
 le conseiller responsable de la contrainte X13 X28 est C1
 le conseiller responsable de la contrainte X37 X28 est C1
 le conseiller responsable de la contrainte X32 X14 est C1
 le conseiller responsable de la contrainte X14 X27 est C1
 le conseiller responsable de la contrainte X13 X24 est C1
 le conseiller responsable de la contrainte X37 X28 est C1
 le conseiller responsable de la contrainte X24 X35 est C1

Aidez moi SVP

Ynora · Answer

Pourquoi ne pas faire un :
if(!t.contains(tonElement)){
t.add(tonElement);
}

Ca devrait te permettre d'éviter les doublons.

sassion · Answer

j'ai utilisé le contains mais ça marche pas dans mon cas car ma recherche doit suivre l'ordre d'apparition des élément deux à deux. et le contains elle s'en fou de l'ordre des élements.

Ynora · Answer

Effectivement.

Dans un premier temps, je sais pas si ta structure de données est imposée, mais, ça me semblerait plus propre pour représenter ton graphe comme étant une liste de couples de sommets.

public class Sommet{
 int idSommet;

 /* */
}

public class Arrete {
 Sommet A;
 Sommet B;

 /* Constructeurs et accesseurs */


 public boolean equals(Object o){
  /* le truc habituel ici */
  Arrete arr = (Arrete) o;
  if((arr.getA().equals(this.getA()) && arr.getB().equals(this.getB()))||
     (arr.getA().equals(this.getB()) && arr.getB().equals(this.getA()))){
      
     // Permet de valider que l'arrete A->B soit égale à l'arrete B->A
     return true;
  } 
 }
}

public class Graph {
 List<Sommet> mes_sommets;
 List mes_arretes;

 public boolean isConnexe(){
   return mes_arretes.size()-1>=mes_sommets.size();
 }

 public boolean isATree(){
   return mes_arretes.size()-1==mes_sommets.size();
 }

}

Le fait de passer par une structure un peu plus élaborée te simplifiera, je pense, ton problème. Car en réimplémentant le 'equals', tu pourras ensuite utiliser le 'contains' sur ta liste.



Si tu souhaites garder ta structure de données... pour éviter les doublons, a mon avis, il faudrait passer par un tableau intermediaire. Et en passant par des identifiants pour tes sommets, qui sont des nombres premiers. Ton tableau intermédiaire stockerai le produit de tes deux identifiants de sommets, qui devrait être unique...

Ensuite, chaque fois que tu souhaite ajouter des valeurs à t, tu verifies que ton tableau intermediaire ne contienne pas le produit de tes deux identifiants de sommets... Ca me semble le truc le plus 'simple' à mettre en place, en conservant ta structure de données actuelle.

Composante connexe

7 réponses

Votre réponse

Discussions similaires