#include <stdio.h> #include <stdlib.h> #include <math.h> #include <assert.h> #include <stdbool.h> #include "common.h" float prim(edge* aretes, int na, int nv){ bool* atteint = malloc(nv * sizeof(bool)); for (int i = 0; i < nv; i+=1){ atteint[i] = false; } // on part du sommet 0 (ou autre ...) atteint[0] = true; float ltot = 0.; /* poids de l'ACM */ for (int tour = 1; tour < nv; tour += 1){ // on cherche l'arete la moins couteuse permettant // d'atteindre un sommet non-atteint à partir d'un sommet atteint int num_a = -1; int poids_a = -1; for (int i = 0; i < na; i += 1){ edge a = aretes[i]; if ((atteint[a.i] && !atteint[a.j]) || (atteint[a.j] && !atteint[a.i])){ assert(!a.selected); if (num_a == -1 || a.d < poids_a) { num_a = i; poids_a = a.d; } } } assert(num_a != -1); // on selectionne l'arete, et on marque le sommet atteint aretes[num_a].selected = true; atteint[aretes[num_a].i] = true; atteint[aretes[num_a].j] = true; ltot += aretes[num_a].d; } free(atteint); return ltot; } int main(int argc, char* argv[]){ printf("Yaourtophone project ! avec l'algo de Prim\n"); assert(argc == 3); const char* fichier_in = argv[1]; const char* fichier_out = argv[2]; /* lecture du fichier */ int n; node* villes = lireFichier(fichier_in, &n); /* création du tableau d'arêtes */ int na; edge* aretes = creerAretes(villes, n, &na); /* algorithme de Prim */ float ltot = prim(aretes, na, n); printf("longueur totale : %f\n", ltot); /* export geojson */ exporter(fichier_out, aretes, na, villes, n); // libération free(villes); free(aretes); return 0; }