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