Calculer le nombre des composantes connexes [Fermé]

Signaler
Messages postés
10
Date d'inscription
lundi 13 février 2017
Statut
Membre
Dernière intervention
20 avril 2017
-
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); } }
  
  
   
   
     
   
    
      }
   
    
  
}}