Discussion :

[arnoctambule]

Bonjour, je viens de trouver un algorithme en java de KRuskal sur internet. Il fonctionne bien mais je ne comprends pas ce qu'il indique en résultat dans la console. Si vous pouvez m'aider, ca serait très sympa.
Merci
Arnaud
Voila l'algo

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

[iohack]

Ta question aurait plutot sa place dans le forum algo !

[pseudocode]

A priori, la sortie représente l'arbre. Chaque ligne se compose de:

[numero du noeud de l'arbre] [noeud de départ du graphe] [noeud d'arrivé du graphe] [poids de la liaison]