Maximum independant set

Fermé
salma_dora - 4 mars 2017 à 22:06
Bonjour,
j'ai une question comment choisit le maximum independant set, voila mon code source pour le MIS mais je ne sais pas comment choisir le max a partir les MISs
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class NewMIS {
	
	static int nbNoeuds=6;
   static  int[][] adjmatrix = {{0,1,1,0,0},{1,0,1,0,0},{1,1,0,0,0},{1,0,0,0,1},{0,0,0,1,0}};
  static  List<Integer> maxIs= new ArrayList<Integer>();
  static  List<Integer> mIS = new ArrayList<Integer>();
      static  List<Integer> VList= new ArrayList<Integer>();
	    public static List<Integer> MIS () {
			
			Random rnd=new Random();
			for ( int iv=0; iv <= nbNoeuds;iv++){
				VList.add(iv);}
				
			while(!VList.isEmpty()){
				int  n=rnd.nextInt(VList.size());
				
				int v=VList.remove(n);
				
				mIS.add(v);
				
				for(int j=1; j<VList.size();j++){
					if(adjmatrix[v][j]==1){
						
						VList.remove(j);
						
					}
				}
			}
			
		
			return mIS;
				} 
	public static void main(String[] args) {
		System.out.println(MIS ());
        
			
	}	}