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