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
| import java.io.* ;
import java.util.* ;
class Arete {
int g,d,p ;
Arete(int g, int d, int p) {
this.g=g; this.d=d; this.p=p; }
}
public class Kruskal {
final static int nNoeuds = 50 ;
final static int nAretes = nNoeuds * nNoeuds ;
static Arete [] graphe = new Arete [nAretes] ; // le graphe de depart
static Arete [] arbre = new Arete [nNoeuds]; // l'arbre final sous
// forme de graphe
static int [] papa = new int [nNoeuds] ; // l'arbre sous forme de
// tableau des peres
static void init (int[] t) { // initialisation des
for (int i=0; i<t.length; i++) // peres a -1
t[i]=-1 ;
}
static void triGraph (Arete [] t, int l) { // tri tout simple
int j; int k;
Arete a;
for (int i=0; i<l; i++) {
j=i;
for (k=j; k<l; k++)
if (t[k].p<t[j].p)
j=k;
a=t[j];
t[j]=t[i];
t[i]=a;
}
return;
}
static int lit () { // lecture d'un entier au clavier
int s;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
try {
s = Integer.parseInt(in.readLine());
}
catch (IOException e) {
s = 0 ;
}
return s;
}
// on verifie si deux noeuds sont deja relies dans les arbres courants
// si c'est non, on relie les deux arbres en plus
static boolean cyclep (int[] t, int a, int b) {
int i=a; int j=b;
while (t[i]>0)
i=t[i];
while (t[j]>0)
j=t[j];
if (i!=j) t[i]=j;
return i!=j;
}
// l'algo de kruskal
// a chaque etape, on enrichie le graphe courant en plus
static boolean kruskal (Arete [] g, int nn, int na, int [] a,
Arete [] arbre) {
init(a);
int ia = 0;
int nb = 0;
while (ia<na && nb < nn ){
if (cyclep(a,g[ia].g,g[ia].d)) {
arbre[nb]=g[ia];
nb++;
}
ia++;
}
return nb==nn-1;
}
// lit un ensemble d'aretes au clavier
static int litGraph (Arete [] g) {
int i = 0;
int a; int b; int p=1 ;
while (p>0) {
System.out.print("Noeud 1 ?");
a=lit();
System.out.println("");
System.out.print("Noeud 2 ?");
b=lit();
System.out.println("");
System.out.print("poids ? (0 pour finir)");
p=lit();
System.out.println("");
if (p>0) {
g[i] = new Arete(a,b,p);
i++;
}
}
return(i);
}
// affichage primaire d'un graphe
static void affGraph (Arete [] g, int n) {
System.out.println("");
for (int j=0; j<n; j++) {
System.out.print(j);
if (g[j]!=null)
System.out.println(" "+g[j].g+" "+g[j].d+" "+g[j].p);
}
}
public static void main (String[] args) {
int nn ; int na;
System.out.print("nombre de noeuds ?");
nn=lit() ;
na = litGraph(graphe) ;
triGraph(graphe,na);
kruskal(graphe,nn,na,papa,arbre);
affGraph(arbre,nn-1);
}
} |
