Calculer le nombre des composantes connexes

Fermé
salma_dora Messages postés 10 Date d'inscription lundi 13 février 2017 Statut Membre Dernière intervention 20 avril 2017 - Modifié par salma_dora le 10/03/2017 à 09:55
Bonjour, j'ai une question sur les graphe non orienté
comment calculer le nombre des composantes connexes dans un graphe non orienté a partir de son matrice adjacence voila mon code mais je ne sais pas s'affiche pas le nombre meme le programme ne parcour pas bien le graphe s'il vous plait aide moi j'ai des jours et je suis à la recherche la solution
import java.util.*;

public class Graph1
{
   /* ------------------------------------------
      Data structure used to represent a graph
      ------------------------------------------ */
   int[][]  adjMatrix;
   int      rootNode = 0;
   static int      NNodes;

   boolean[] visited; 

   /* -------------------------------
      Construct a graph of N nodes
      ------------------------------- */
   Graph1(int N)
   {
      NNodes = N;
      adjMatrix = new int[N][N];
      visited = new boolean[N];
   }

   Graph1(int[][] mat)
   {
      int i, j;

      NNodes = mat.length;

      adjMatrix = new int[NNodes][NNodes];
      visited = new boolean[NNodes];


      for ( i=0; i < NNodes; i++)
         for ( j=0; j < NNodes; j++)
            adjMatrix[i][j] = mat[i][j];
   }

   public void dfs(int i)
   {
      int j;

      visited[i] = true;

      printNode(i);

      for ( j = 0; j < NNodes; j++ )
      {
  if ( adjMatrix[i][j] > 0 && !visited[j] )
            dfs(j);
      }
   }


public static void main(String[] args)
{

 int[][] conn = {{0,1,1,0,0,0},  // 0
   { 1,0,1,0,0,0},  // 1
    
   { 1,1,0,0,0,0},  // 2
   { 0,0,0,0,1,0},  // 3
   { 0,0,0,1,0,0},  // 4
   { 0,0,0,0,0,0},  // 5
   };
   
     List<Integer> VList= new ArrayList<Integer>();
     Graph1 G = new Graph1(conn);
     for (int iv=0; iv <= NNodes;iv++){
   VList.add(iv);}
     System.out.println(VList);
  while(!VList.isEmpty()){
   
   Random rnd=new Random();
  int n=rnd.nextInt(VList.size());
  VList.remove(n);
   System.out.println("composant");
   G.dfs(n);
   int k=0;
  k=k+1;
 System.out.println("nombre des composantes connexes :"+k);
  for(int j=0; j<VList.size();j++){
   if(conn[n][j]==1){
   VList.remove(j); } }
  
  
   
   
     
   
    
      }
   
    
  
}}