IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Java Discussion :

Arbre de recouvrement minimal Prim


Sujet :

Langage Java

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : Mars 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut Arbre de recouvrement minimal Prim
    Bonjour,

    Je suis bloqué sur mon code java : mon but est de faire un MST (arbre de recouvrement minimal) avec l'algorithme de Prim : je peux déja tracer un réseaux avec un ensemble de points mais je ne sais pas comment tracer le chemin ?

    Voici mon code du fichier AppliMST.java :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    import javax.swing.*;
    import java.awt.*;
    import java.awt.event.*;
    import java.util.*;
    import java.lang.*; //où il y a la classe prim
     
    class Point{
    	double x=0.0;
    	double y=0.0;
    	public Point(double a, double b){
    		x=a;
    		y=b;
    	}
    }
     
    class Reseau{
    	Point[] lesPoints= null;
    	Lien[] lesLiens=null;
    	public Reseau(int combien, int nblien){    //combien= de point et nblien = nombre de lien
    		Random gen = new Random();  
    		lesPoints = new Point[combien];
    		double x;
    		double y;
    		for(int i=0; i<combien; i++){
    			x = gen.nextDouble();
    			y = gen.nextDouble();
    			lesPoints[i]= new Point(x, y);			
    		}
    		Random r=new Random();
    		lesLiens = new Lien[nblien];
    		for(int i=0; i<nblien; i++){
    			Point pt1 = lesPoints[r.nextInt(combien)];
    			Point extrem = lesPoints[r.nextInt(combien)];
    			lesLiens[i]= new Lien(pt1, extrem);
    		}
    	}
    }
     
    class Lien{
    	Point origine=null;
    	Point extrem=null;
    	double lienance=0.0;
    	public Lien(Point a, Point b){
    		origine=a;
    		extrem=b;
    		lienance=Math.sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
    	}
    }
    class Dessin extends JPanel {
    	private int largeur = 0; // attributs du dessin
    	private int hauteur = 0;
    	private int left = 0;
    	private int top = 0;
    	private int taille = 15;
    	private int nbl = (((taille-2)*(taille-1))/2) +1;
    	private Reseau monReseau = new Reseau(taille, nbl);
     
    	public void paint(Graphics g) { // la méthode appelée par défaut pour dessiner
    		largeur= getWidth()-20;
    		hauteur= getHeight()-20;
    		left=10;
    		top=10;
    		g.setColor(Color.WHITE);
    		g.fillRect(left, top, largeur, hauteur);
    		g.setColor(Color.black);
    		int a;
    		int b;
    		int x0;
    		int y0;
    		int xe;
    		int ye;
    		for(int i=0; i<taille; i++){
    			a = (int)(monReseau.lesPoints[i].x*largeur + left);
    			b = (int)(monReseau.lesPoints[i].y*hauteur + top);			
    			g.drawLine(a-2, b, a+2, b);
    			g.drawLine(a, b-2, a, b+2);			
    		}
    		for(int i=0; i<nbl; i++){
    			x0 = (int)(monReseau.lesLiens[i].origine.x*largeur + left);
    			y0 = (int)(monReseau.lesLiens[i].origine.y*hauteur + top);
    			xe = (int)(monReseau.lesLiens[i].extrem.x*largeur + left);
    			ye = (int)(monReseau.lesLiens[i].extrem.y*hauteur + top);
    			g.drawLine(x0, y0, xe, ye);
    		}
    	}
    }
    public class Prim {
    	public static int [] prim (WeightedGraph G, int s) {
            final int [] lien = new int [G.size()];  // lienance la plus courte pour le MST
            final int [] pred = new int [G.size()];  // precedent l'abre
            final boolean [] visited = new boolean [G.size()];
     
            for (int i=0; i<lien.length; i++) {
               lien[i] = Integer.MAX_VALUE;
            }
            lien[s] = 0;
     
            for (int i=0; i<lien.length; i++) {
               final int next = minPoint (lien, visited);
               visited[next] = true;
     
               final int [] n = G.neighbors (next);
               for (int j=0; j<n.length; j++) {
                  final int v = n[j];
                  final int d = G.getWeight(next,v);
                  if (lien[v] > d) {
                    lien[v] = d;
                    pred[v] = next;
                  }
               }
            }
            return pred;
         }
     
         private static int minPoint (int [] lien, boolean [] v) {
            int x = Integer.MAX_VALUE;
            int y = -1;
            for (int i=0; i<lien.length; i++) {
               if (!v[i] && lien[i]<x) {y=i; x=lien[i];}
            }
            return y;
         }
      }
     
     
    public class AppliMST {
    	public static void main(String[] args) {
    		// Créer une fenêtre, y placer un dessin et afficher
    		JFrame fenetre = new JFrame("Une application graphique");
    		fenetre.setSize(200, 200);
    		Dessin dessin = new Dessin();
    		fenetre.getContentPane().add(dessin);
    		fenetre.setVisible(true);
     
     
    		fenetre.addWindowListener(new WindowAdapter(){
    			public void windowClosing(WindowEvent we){
    				System.exit(0);
    			}
    		});
    	}
    }




    MERCI d'avance

  2. #2
    Modérateur
    Avatar de wax78
    Homme Profil pro
    Chef programmeur
    Inscrit en
    Août 2006
    Messages
    4 084
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Belgique

    Informations professionnelles :
    Activité : Chef programmeur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2006
    Messages : 4 084
    Points : 7 998
    Points
    7 998
    Par défaut
    N'oublies pas la balise de CODE pour ton code.

    Tu n'as pas la classe WeightedGraph ? pour pouvoir essayer plus facilement et comprendre.

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : Mars 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut
    Voila
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
     import javax.swing.*;
    import java.awt.*;
    import java.awt.event.*;
    import java.util.*;
    import java.lang.*; //où il y a la classe Prim
     
    class Point{
    	double x=0.0;
    	double y=0.0;
    	public Point(double a, double b){
    		x=a;
    		y=b;
    	}
    }
     
    class Reseau{
    	Point[] lesPoints= null;
    	Lien[] lesLiens=null;
    	public Reseau(int combien, int nblien){    //combien= de point et nblien = nombre de lien
    		Random gen = new Random();  
    		lesPoints = new Point[combien];
    		double x;
    		double y;
    		for(int i=0; i<combien; i++){
    			x = gen.nextDouble();
    			y = gen.nextDouble();
    			lesPoints[i]= new Point(x, y);			
    		}
    		Random r=new Random();
    		lesLiens = new Lien[nblien];
    		for(int i=0; i<nblien; i++){
    			Point pt1 = lesPoints[r.nextInt(combien)];
    			Point extrem = lesPoints[r.nextInt(combien)];
    			lesLiens[i]= new Lien(pt1, extrem);
    		}
    	}
    }
     
    class Lien{
    	Point origine=null;
    	Point extrem=null;
    	double lienance=0.0;
    	public Lien(Point a, Point b){
    		origine=a;
    		extrem=b;
    		lienance=Math.sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
    	}
    }
    class Dessin extends JPanel {
    	private int largeur = 0; // attributs du dessin
    	private int hauteur = 0;
    	private int left = 0;
    	private int top = 0;
    	private int taille = 15;
    	private int nbl = (((taille-2)*(taille-1))/2) +1;
    	private Reseau monReseau = new Reseau(taille, nbl);
     
    	public void paint(Graphics g) { // la méthode appelée par défaut pour dessiner
    		largeur= getWidth()-20;
    		hauteur= getHeight()-20;
    		left=10;
    		top=10;
    		g.setColor(Color.WHITE);
    		g.fillRect(left, top, largeur, hauteur);
    		g.setColor(Color.black);
    		int a;
    		int b;
    		int x0;
    		int y0;
    		int xe;
    		int ye;
    		for(int i=0; i<taille; i++){
    			a = (int)(monReseau.lesPoints[i].x*largeur + left);
    			b = (int)(monReseau.lesPoints[i].y*hauteur + top);			
    			g.drawLine(a-2, b, a+2, b);
    			g.drawLine(a, b-2, a, b+2);			
    		}
    		for(int i=0; i<nbl; i++){
    			x0 = (int)(monReseau.lesLiens[i].origine.x*largeur + left);
    			y0 = (int)(monReseau.lesLiens[i].origine.y*hauteur + top);
    			xe = (int)(monReseau.lesLiens[i].extrem.x*largeur + left);
    			ye = (int)(monReseau.lesLiens[i].extrem.y*hauteur + top);
    			g.drawLine(x0, y0, xe, ye);
    		}
    	}
    }
    public class Prim {
    	public static int [] prim (WeightedGraph G, int s) {
            final int [] lien = new int [G.size()];  // lienance la plus courte pour le MST
            final int [] pred = new int [G.size()];  // precedent l'abre
            final boolean [] visited = new boolean [G.size()];
     
            for (int i=0; i<lien.length; i++) {
               lien[i] = Integer.MAX_VALUE;
            }
            lien[s] = 0;
     
            for (int i=0; i<lien.length; i++) {
               final int next = minPoint (lien, visited);
               visited[next] = true;
     
               final int [] n = G.neighbors (next);
               for (int j=0; j<n.length; j++) {
                  final int v = n[j];
                  final int d = G.getWeight(next,v);
                  if (lien[v] > d) {
                    lien[v] = d;
                    pred[v] = next;
                  }
               }
            }
            return pred;
         }
     
         private static int minPoint (int [] lien, boolean [] v) {
            int x = Integer.MAX_VALUE;
            int y = -1;
            for (int i=0; i<lien.length; i++) {
               if (!v[i] && lien[i]<x) {y=i; x=lien[i];}
            }
            return y;
         }
      }
     
     
    public class AppliMST {
    	public static void main(String[] args) {
    		// Créer une fenêtre, y placer un dessin et afficher
    		JFrame fenetre = new JFrame("Une application graphique");
    		fenetre.setSize(200, 200);
    		Dessin dessin = new Dessin();
    		fenetre.getContentPane().add(dessin);
    		fenetre.setVisible(true);
     
     
    		fenetre.addWindowListener(new WindowAdapter(){
    			public void windowClosing(WindowEvent we){
    				System.exit(0);
    			}
    		});
    	}
    }
    Je ne connais pas cette classe. Attend je regarde dans la javadoc =)

  4. #4
    Modérateur
    Avatar de wax78
    Homme Profil pro
    Chef programmeur
    Inscrit en
    Août 2006
    Messages
    4 084
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Belgique

    Informations professionnelles :
    Activité : Chef programmeur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2006
    Messages : 4 084
    Points : 7 998
    Points
    7 998
    Par défaut
    En fait tu ne t'en sert pas je ne l'avais pas vu au début.

  5. #5
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : Mars 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut
    En fait c'est un exo en informatique que je fais toutes les semaines, c'est pour cela que je n'ai pas répondu avant et ... que je n'ai pas avancer depuis. Je cherche toujours à mettre l'algo de Prim dans mon code. Mais comment faire ?

Discussions similaires

  1. Arbre recouvrant de poids minimum
    Par helamal dans le forum Débuter avec Java
    Réponses: 2
    Dernier message: 02/01/2013, 20h46
  2. [Débutant] arbre couvrant minimal - algorithme de Prim
    Par idées dans le forum MATLAB
    Réponses: 0
    Dernier message: 27/10/2011, 11h32
  3. Arbre couvrant minimal (ACM) : insertion de nœuds pour minimiser le poids total
    Par thinkbig dans le forum Intelligence artificielle
    Réponses: 0
    Dernier message: 13/06/2011, 22h40
  4. arbre minimal a partir d'un document xml
    Par veerzara dans le forum Débuter
    Réponses: 1
    Dernier message: 31/05/2011, 14h26
  5. Arbre couvrant minimal
    Par yaris20 dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 18/08/2008, 14h31

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo