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);
}
});
}
} |
