Bonjour, je dois coder un algorithme de Prim Jarnik a l'aide d'arrayList en utilisant les classes ci-dessous et en complétant le premier code:

/* Version de l'algorithme de Prim-Jarnik utilisant
une ArrayList pour les aretes et aussi pour les sommets rejoints

Graphe: aretes spécifiees par matrice de distances
*/

import java.util.*;

public class Main_reseau_fibre {    
    public static void main(String[] args){
        
        int nbSommets = 7;
        
        // matrice des distances entre sommets
        int [][] matDist = {
            { 0, 30, 40, 50, 20, 50, 20},
            {30,  0, 30,  0, 50,  0,  0},
            {40, 30,  0, 20, 50,  0,  0},
            {50,  0, 20,  0, 40,  0,  0},
            {20, 50, 50, 40,  0, 40, 30},
            {50,  0,  0,  0, 40,  0,  0},
            {20,  0,  0,  0, 30,  0,  0}};
        
        
        // representation de l'ensemble S de l'algorithme
        // par la liste suivante:
        ArrayList<Arete> lesAretes = new ArrayList<Arete>();
        ArrayList<Arete> couvertureMinimale = new ArrayList<Arete>();
        
        // construction de l'ensemble des aretes a partir de
        // la matrice de distances
        for(int i=0;i<nbSommets-1;i++){
            for(int j=i+1;j<nbSommets;j++){
                if (matDist[i][j] != 0){
                    Arete uneArete = new Arete(i,j,matDist[i][j]);
                    lesAretes.add(uneArete);
                    
                    System.out.println(uneArete); // Pour voir les aretes dans la console
                    
                }
            }
        }

        // representation de l'ensemble R de l'algorithme
        // par la liste suivante:
        ArrayList<Integer> lesSommetsRejoints = new ArrayList<Integer>();
        
        // ATTENTION c'est bien Integer et non int
        
        // initialisation
        lesSommetsRejoints.add(0);
        
        
        // COMPLETER LE CODE ICI
        Arete nouvelle;
        int nb=0;
        
        lesAretes.sort(Comparator.comparingInt(Arete::getPoids));
        
        
        
        while(lesSommetsRejoints.size()<nbSommets)
        {
			System.out.println();
			for(Arete a : lesAretes)
			{
				 if(lesSommetsRejoints.contains(a.sommetA) && lesSommetsRejoints.contains(a.sommetB)==false)
				 {
					System.out.println(a+" poids "+a.poids);
					lesSommetsRejoints.add(a.sommetB);
					couvertureMinimale.add(new Arete(a.sommetA, a.sommetB, a.poids));
				 }
				 else if(lesSommetsRejoints.contains(a.sommetB) && lesSommetsRejoints.contains(a.sommetA)==false)
				 {
					 System.out.println(a+" poids "+a.poids);
					 lesSommetsRejoints.add(a.sommetA);
					 couvertureMinimale.add(new Arete(a.sommetB, a.sommetA, a.poids));
				 }
			}
			System.out.println(lesAretes.size());
			
		}
        
        
        
    }
  }

public class Arete implements Comparable<Arete>{

    // Une arete relie deux sommets, elle n'a pas de sens privilegie.
    // Les sommets sont reperes par un numero.
    
    public int sommetA; // Le sommet ayant le plus petit numero des deux.
    public int sommetB; // Le sommet ayant le plus grand numero des deux.
    public int poids;
    
    public Arete(int unSommet, int autreSommet, int unPoids){
        sommetA = Math.min(unSommet,autreSommet);
        sommetB = Math.max(unSommet,autreSommet);
        poids = unPoids;
    }
    
    public String toString(){
        return "Arete du sommet "+sommetA+" au sommet "+sommetB;
    }

	public int getPoids(){return poids;}

    // Definitions des methodes de test d'egalite et de comparaison
    // en assurant la coherence entre les deux
    // c'est a dire: 'compareTo' renvoie 0 si est seulement
    // si 'equals' renvoie 'true'
    
    public boolean equals(Arete autreArete){
    
        return ((this.sommetA == autreArete.sommetA)
            && (this.sommetB == autreArete.sommetB)
            && (this.poids == autreArete.poids));
    }
    
    public int compareTo(Arete autreArete){
    
        // critere principal sur le poids
        if (this.poids < autreArete.poids){
            return -1;
        }else if (this.poids > autreArete.poids){
            return 1;
        }else{
            // dans le cas ou les poids sont egaux
            // pour maintenir la coherence avec 'equals'
            // on utilise un critere de comparaison sur
            // les numeros des sommets A et B
            
            if (this.sommetA < autreArete.sommetA){
                return -1;
            }else if (this.sommetA > autreArete.sommetA){
                return 1;
            // les sommets A sont les memes, on continue en
            // comparant les sommets B
            }else if (this.sommetB < autreArete.sommetB){
                return -1;
            }else if (this.sommetB > autreArete.sommetB){
                return 1;
            }else{
                return 0;
            }
        }
    }
    
}

-
Edité par 961Youssef 15 février 2021 à 21:52:11

T'es sûr de celle-ci ? :

for(int j=i+1;j<nbSommets;j++){ 

-
Edité par BuRner 27 février 2021 à 12:27:26