#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define INFINITY 1000000 // or set e.g. INFINITY = INT_MAX - max_weight_graph(G);
// ----------------------------------definition des structures-----------------------------------------
//----------------------------------------Structure Graphe---------------------------------------------------------
typedef struct _noeud
{
int id; // Identifiant du nœud de destination.
int poids; // Poids de l'arc menant à ce nœud.
struct _noeud* successeur; // Pointeur vers le prochain nœud successeur dans la liste.
} Noeud;
// Définition d'une structure pour représenter un graphe.
typedef struct
{
int nb_noeuds; // Nombre total de nœuds dans le graphe.
Noeud** liste_successeurs; // Tableau de pointeurs vers les listes de successeurs de chaque nœud.
} Graphe;
//-------------------------------------------Structure Liste------------------------------------------------------
// Définition de la structure d'un élément de la liste chaînée
typedef struct _element
{
int id; // Identifiant ou valeur stockée par l'élément de la liste.
struct _element *suivant; // Pointeur vers le prochain élément de la liste, permettant de créer une chaîne d'éléments.
} Element;
// Définition de la structure pour une liste chaînée
typedef struct
{
Element *tete; // Pointeur vers le premier élément de la liste, permettant l'accès à tous les éléments en chaîne.
} Liste;
//-------------------------------------------Structure Tas------------------------------------------------------
// Structure représentant un élément de tas
typedef struct
{
int id; // Identifiant unique de l'élément
float valeur; // Valeur associée à l'élément, utilisée pour le tri dans le tas
} ElementTas;
// Structure représentant un tas
typedef struct
{
ElementTas* tableau; // Tableau d'éléments stockés dans le tas
int taille; // Taille actuelle du tas, indique le nombre d'éléments stockés
} Tas;
//-------------------------------------------Structure Kruskal------------------------------------------------------
// Structure représentant une arête, si nécessaire dans votre contexte
typedef struct arete
{
int sommet1; // Sommet de départ
int sommet2; // Sommet d'arrivée
int poids; // Poids de l'arête
} Arete;
// La structure Graphe reste inchangée, adaptée à votre contexte d'utilisation
// Structure pour un nœud dans une liste d'arêtes, si nécessaire
typedef struct noeudListe
{
Arete arete; // L'arête stockée dans le nœud
struct noeudListe* successeur; // Pointeur vers le prochain nœud dans la liste
} NoeudListe;
// Structure pour une liste d'arêtes, si nécessaire
typedef struct listeAretes
{
NoeudListe* tete; // Pointeur vers le premier nœud de la liste
} ListeAretes;
typedef struct graphe {
int nb_sommets; // Nombre total de sommets dans le graphe.
int nb_aretes; // Nombre total d'arêtes dans le graphe.
Arete* liste_aretes; // Tableau d'arêtes.
} Graphe_kruskal;
//------------------------------------Déclaration des fonctions-------------------------------------------
// -------------------------------Fonctions tri --------------------------------------
void tri_fusion(Noeud* tab, int deb, int fin) ;
void fusion(Noeud* tab, int deb, int fin1, int fin) ;
// -------------------------------Fonctions pour la gestion du graphe--------------------------------------
void Cree_graphe_oriente_a_partir_de_fichier(Graphe* G, const char* nomFichierGraphe);
void creer_graphe_non_oriente_a_partir_de_fichier(Graphe* G, const char* nomFichierGraphe);
void afficher_graphe(Graphe* G);
int trouver_poids_minimal(Graphe* graphe);
int trouver_poids_maximal(Graphe* graphe);
void ajoute_arete_oriente_liste_avec_poids(Graphe* graphe, int sommet1, int sommet2, int poids);
void ajoute_arete_non_oriente_liste_avec_poids(Graphe* graphe, int sommet1, int sommet2, int poids);
void ajoute_arete_non_oriente_liste(Graphe* graphe, int sommet1, int sommet2);
void ajoute_arete_oriente_liste(Graphe* graphe, int sommet1, int sommet2);
// --------------------------------------Fonctions pour la gestion de la liste--------------------------------------
void initialiser_liste(Liste *liste);
void ajouter_en_tete_de_liste(Liste *liste, int identifiant);
bool est_vide(Liste *liste);
void supprimer_element(Liste *liste, int id_element);
void affiche_liste(Liste *liste);
int obtenir_id_tete(Liste *liste);
bool est_dans_liste(Liste* liste, int id_element);
int obtenir_indice_min_dans_liste(int* distances, Liste *liste);
void supprimer_tete(Liste *liste);
void liberer_liste(Liste *liste);
//--------------------------------------Fonctions pour les tas--------------------------------------
// Initialisation et création d'un tas
void creer_tas_vide(Tas *tas, int taille_max);
void creer_tas(Tas *tas, ElementTas *tableau_elements, int taille_reelle, int taille_max);
// Opérations sur les indices dans un tas
int indice_fils_gauche(int indice_cellule);
int indice_fils_droit(int indice_cellule);
int indice_parent(int indice_cellule);
// Fonctions auxiliaires pour gérer les propriétés du tas
int nb_enfants(Tas *tas, int indiceCellule);
ElementTas enfant_gauche(Tas *tas, int indiceCellule);
ElementTas enfant_droit(Tas *tas, int indiceCellule);
ElementTas contenu_cellule(Tas *tas, int indiceCellule);
bool est_dans_tas(Tas *tas, int id);
int obtenir_indice_dans_tas(Tas *tas, ElementTas element);
void echanger_avec_parent(Tas *tas, int indiceCellule);
// Fonctions principales pour manipuler le tas
void remonter(Tas *tas, int indiceElement);
void descendre(Tas *tas, int indiceElement);
void inserer_dans_tas(Tas *tas, ElementTas nouvelElement);
ElementTas extraire_min(Tas *tas);
ElementTas extraire_max(Tas *tas); // À adapter si votre implémentation est spécifiquement pour un tas min
void mettre_a_jour_priorite(Tas *tas, ElementTas nouvelElement);
// Affichage du contenu du tas
void affiche_tas(Tas *tas);
// --------------------------------------Fonctions de l'algorithme de Dijkstra--------------------------------------
void dijkstra_initialiser(Graphe* G, int* tableau_distances, bool* tableau_visites, int source);
void dijkstra_sans_tas(Graphe* graphe, int source, int* tableau_distances);
void dijkstra_avec_tas(Graphe* G, int source, int* tableau_distances);
// --------------------------------------Fonction pour l'algo de Prim--------------------------------------
void prim_initialiser(Graphe* G, int* tableau_distances, int* tableau_parents);
int prim(Graphe* G, int* tableau_distances, int* tableau_parents) ;
void prim_sans_tas(Graphe* G, int* tableau_distances, int* tableau_parents) ;
// ----------------Fonction pour Bellman Ford (uniquement implémentable avec des listes --------------------------------------
bool bellman_ford(Graphe* G, int source, int* tableau_distances);
// Fonctions
// Fonction qui initialise djikistra
//---------------------------------------Graphe-----------------------------------------------------------
//----------------------------------Fonction globale---------------------------------------------------
// Fonction qui cree un graphe oriente à partir d'un fichier
void Cree_graphe_oriente_a_partir_de_fichier(Graphe* G, const char* nomFichierGraphe)
{
FILE *fichier = fopen(nomFichierGraphe, "r"); // Ouvre le fichier contenant les données du graphe en lecture.
if (fichier != NULL) // Si le fichier a été ouvert avec succès...
{
int nb_noeuds, nb_arcs, noeud_depart, noeud_arrivee, poids_arc;
fscanf(fichier, "%d %d", &nb_noeuds, &nb_arcs); // Lit le nombre total de noeuds et d'arcs du graphe.
G->nb_noeuds = nb_noeuds; // Stocke le nombre de noeuds dans la structure Graphe.
G->liste_successeurs = (Noeud**) malloc(nb_noeuds * sizeof(Noeud*)); // Alloue de l'espace pour les listes de successeurs de chaque noeud.
for (int i = 0; i < nb_noeuds; i++)
G->liste_successeurs[i] = NULL; // Initialise chaque liste de successeurs comme vide.
for (int i = 0; i < nb_arcs; i++)
{
fscanf(fichier, "%d %d %d", &noeud_depart, &noeud_arrivee, &poids_arc); // Lit les informations de chaque arc: noeud de départ, d'arrivée et poids.
Noeud* nouveau_noeud = (Noeud*) malloc(sizeof(Noeud)); // Alloue de la mémoire pour un nouveau noeud successeur.
nouveau_noeud->id = noeud_arrivee; // Affecte l'ID du noeud d'arrivée.
nouveau_noeud->poids = poids_arc; // Affecte le poids de l'arc au nouveau noeud.
// Insère le nouveau noeud en tête de la liste des successeurs du noeud de départ.
nouveau_noeud->successeur = G->liste_successeurs[noeud_depart];
G->liste_successeurs[noeud_depart] = nouveau_noeud;
}
} else printf("Le fichier n'a pas été trouvé."); // Affiche un message d'erreur si le fichier ne peut pas être ouvert.
fclose(fichier); // Ferme le fichier une fois le traitement terminé.
}
// Fonction qui cree un graphe non oriente avec 2 noeuds à partir d'un fichier
void creer_graphe_non_oriente_a_partir_de_fichier(Graphe* G, const char* nomFichierGraphe)
{
FILE *fichier;
fichier = fopen(nomFichierGraphe, "r"); // Ouvre le fichier contenant les données du graphe en mode lecture.
if (fichier != NULL) // Vérifie si le fichier a été ouvert avec succès.
{
int nb_noeuds, nb_arcs, noeud_depart, noeud_arrivee, poids;
fscanf(fichier, "%d %d", &nb_noeuds, &nb_arcs); // Lit le nombre de noeuds et d'arcs du graphe depuis le fichier.
G->nb_noeuds = nb_noeuds; // Initialise le nombre de noeuds dans la structure Graphe.
G->liste_successeurs = (Noeud**) malloc(nb_noeuds * sizeof(Noeud*)); // Alloue de l'espace pour les listes de successeurs.
for (int i = 0; i < nb_noeuds; i++)
G->liste_successeurs[i] = NULL; // Initialise chaque liste de successeurs à NULL.
for (int i = 0; i < nb_arcs; i++)
{
fscanf(fichier, "%d %d %d", &noeud_depart, &noeud_arrivee, &poids); // Lit les données de chaque arc du fichier.
// Crée le noeud pour l'arête de noeud_depart vers noeud_arrivee
Noeud* nouveau_noeud1 = (Noeud*) malloc(sizeof(Noeud));
nouveau_noeud1->id = noeud_arrivee - 1;
nouveau_noeud1->poids = poids;
nouveau_noeud1->successeur = G->liste_successeurs[noeud_depart - 1];
G->liste_successeurs[noeud_depart - 1] = nouveau_noeud1;
// Crée le noeud pour l'arête de noeud_arrivee vers noeud_depart pour rendre le graphe non orienté
Noeud* nouveau_noeud2 = (Noeud*) malloc(sizeof(Noeud));
nouveau_noeud2->id = noeud_depart - 1;
nouveau_noeud2->poids = poids;
nouveau_noeud2->successeur = G->liste_successeurs[noeud_arrivee - 1];
G->liste_successeurs[noeud_arrivee - 1] = nouveau_noeud2;
}
}
else printf("Le fichier n'a pas été trouvé.\n"); // Affiche un message d'erreur si le fichier n'est pas trouvé.
fclose(fichier); // Ferme le fichier après l'avoir lu.
}
// Fonction qui affiche le graphe
void afficher_graphe(Graphe* G)
{
for(int i = 0; i < G->nb_noeuds; i++) // Parcourt tous les nœuds du graphe
{
printf("Noeud %d : ", i+1); // Affiche le numéro du nœud courant
Noeud* courant = G->liste_successeurs[i]; // Initialisation du pointeur vers le premier successeur du nœud courant
while(courant != NULL) // Parcourt la liste des successeurs du nœud courant
{
printf("%d, ", courant->id+1);// Affiche l'ID (numéro) du successeur, ajusté pour l'affichage (index+1 au lieu de index)
// On peut mettre le +1 ou non
courant = courant->successeur;// Passe au successeur suivant dans la liste
}
printf("\n\n");// Insère deux sauts de ligne après avoir listé tous les successeurs d'un nœud
}
}
//Fonction qui trouve le poids maximal parmi toutes les arêtes du graphe ( arête avec le + gros poids)
int trouver_poids_maximal(Graphe* graphe)
{
int poids_maximal = 0; // On peut commencer avec INT_MIN pour les poids neg et initialisation du poids maximal à 0 pour débuter la recherche
for(int i = 0; i < graphe->nb_noeuds; i++) // Boucle à travers tous les nœuds du graphe
{
Noeud* noeud_courant = graphe->liste_successeurs[i]; // Pointeur vers le premier noeud successeur du nœud courant
while(noeud_courant != NULL) // Boucle à travers la liste des successeurs du nœud courant
{
if (poids_maximal < noeud_courant->poids)// Si le poids du noeud courant est supérieur au poids maximal actuel, le met à jour
poids_maximal = noeud_courant->poids;
noeud_courant = noeud_courant->successeur; // Passe au successeur suivant dans la liste
}
}
return poids_maximal; // Retourne le poids maximal trouvé
}
// Fonction qui trouve le poids minimal parmi toutes les arêtes du graphe
int trouver_poids_minimal(Graphe* graphe)
{
int poids_minimal = INT_MAX; // Initialisation du poids minimal à la valeur maximale entière pour débuter la recherche
for(int i = 0; i < graphe->nb_noeuds; i++) // Boucle à travers tous les nœuds du graphe
{
Noeud* noeud_courant = graphe->liste_successeurs[i]; // Pointeur vers le premier noeud successeur du nœud courant
while(noeud_courant != NULL) // Boucle à travers la liste des successeurs du nœud courant
{
if (poids_minimal > noeud_courant->poids) // Si le poids du noeud courant est inférieur au poids minimal actuel, le met à jour
poids_minimal = noeud_courant->poids;
noeud_courant = noeud_courant->successeur; // Passe au successeur suivant dans la liste
}
}
// Retourne le poids minimal trouvé, ou INT_MAX s'il n'y a aucune arête
return (poids_minimal == INT_MAX) ? 0 : poids_minimal;
}
//Fonction qui ajoute une arrete avec un poids pour un graphe non orienté
void ajoute_arete_non_oriente_liste_avec_poids(Graphe* graphe, int sommet1, int sommet2, int poids)
{
Noeud* nouveauNoeud1 = (Noeud*)malloc(sizeof(Noeud));// Crée un nouveau nœud pour l'arête de sommet1 à sommet2 avec un poids spécifié.
if (nouveauNoeud1 == NULL)
{
fprintf(stderr, "Erreur d'allocation de mémoire pour le nouveau nœud 1.\n");
return; // En cas d'échec de l'allocation, on quitte la fonction.
}
nouveauNoeud1->id = sommet2;
nouveauNoeud1->poids = poids; // Définit le poids de l'arête.
nouveauNoeud1->successeur = graphe->liste_successeurs[sommet1]; // Insère le nœud au début de la liste.
graphe->liste_successeurs[sommet1] = nouveauNoeud1;
Noeud* nouveauNoeud2 = (Noeud*)malloc(sizeof(Noeud)); // Répète le processus pour l'arête de sommet2 à sommet1 avec le même poids pour maintenir la non orientation.
if (nouveauNoeud2 == NULL)
{
fprintf(stderr, "Erreur d'allocation de mémoire pour le nouveau nœud 2.\n");
free(nouveauNoeud1); // Libération du premier nœud alloué en cas d'échec de la deuxième allocation.
return; // En cas d'échec de l'allocation, on quitte la fonction.
}
nouveauNoeud2->id = sommet1;
nouveauNoeud2->poids = poids; // Définit le poids de l'arête.
nouveauNoeud2->successeur = graphe->liste_successeurs[sommet2]; // Insère le nœud au début de la liste.
graphe->liste_successeurs[sommet2] = nouveauNoeud2;
}
// Fonction qui ajoute une arrete avec un poids pour un graphe orienté
void ajoute_arete_oriente_liste_avec_poids(Graphe* graphe, int sommet1, int sommet2, int poids)
{
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));// Crée un nouveau nœud pour l'arête de sommet1 à sommet2 avec un poids spécifié.
if (nouveauNoeud == NULL)
{
fprintf(stderr, "Erreur d'allocation de mémoire pour le nouveau nœud.\n");
return; // En cas d'échec de l'allocation, on quitte la fonction.
}
nouveauNoeud->id = sommet2;
nouveauNoeud->poids = poids; // Définit le poids de l'arête.
nouveauNoeud->successeur = graphe->liste_successeurs[sommet1]; // Insère le nœud au début de la liste de successeurs de sommet1.
graphe->liste_successeurs[sommet1] = nouveauNoeud;
}
//fonction qui ajoute une arete sans poids pour une liste et un graphe non oriente
void ajoute_arete_non_oriente_liste(Graphe* graphe, int sommet1, int sommet2) // Crée un nouveau nœud pour l'arête de sommet1 à sommet2.
{
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Alloue de la mémoire pour le nouveau nœud.
nouveauNoeud->id = sommet2 ; // Assigne sommet2 comme l'ID du nœud de destination.
nouveauNoeud->successeur = graphe->liste_successeurs[sommet1] ; // Le nouveau nœud pointe vers le successeur actuel de sommet1.
graphe->liste_successeurs[sommet1] = nouveauNoeud ; // Fait du nouveau nœud le premier successeur de sommet1.
// Répète le processus pour ajouter un nœud de sommet2 à sommet1 pour maintenir la non orientation du graphe.
nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Alloue de la mémoire pour un autre nouveau nœud.
nouveauNoeud->id = sommet1; // Assigne sommet1 comme l'ID du nœud de destination.
nouveauNoeud->successeur = graphe->liste_successeurs[sommet2]; // Le nouveau nœud pointe vers le successeur actuel de sommet2.
graphe->liste_successeurs[sommet2] = nouveauNoeud; // Fait du nouveau nœud le premier successeur de sommet2.
}
// Fonction pour ajouter une arête orientée de sommet1 vers sommet2 dans un graphe orienté sans poids .
void ajoute_arete_oriente_liste(Graphe* graphe, int sommet1, int sommet2)
{
// Crée un nouveau nœud pour l'arête de sommet1 à sommet2.
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Alloue de la mémoire pour le nouveau nœud.
nouveauNoeud->id = sommet2; // Assigne sommet2 comme l'ID du nœud de destination.
nouveauNoeud->successeur = graphe->liste_successeurs[sommet1]; // Fait pointer le nouveau nœud vers le successeur actuel de sommet1.
graphe->liste_successeurs[sommet1] = nouveauNoeud; // Fait du nouveau nœud le premier successeur de sommet1.
}
//---------------------------------------------- Tri fusion kruskal ------------------------------------------------------
// Fonction pour trier un tableau d'arêtes entre les indices deb et fin
// en utilisant l'algorithme de tri fusion.
// Paramètres :
// - tab : tableau d'arêtes à trier.
// - deb : indice de début de la partie du tableau à trier.
// - fin : indice de fin de la partie du tableau à trier.
void tri_fusion(Noeud* tab, int deb, int fin)
{
int lg = fin - deb + 1; // Calcul de la longueur de la partie du tableau à trier.
int moitie = deb + lg / 2 - 1; // Calcul de l'indice de la moitié (pour diviser le tableau).
// Si la longueur est supérieure à 1, on peut encore diviser.
if (lg > 1)
{
tri_fusion(tab, deb, moitie); // Tri de la première moitié.
tri_fusion(tab, moitie + 1, fin); // Tri de la deuxième moitié.
fusion(tab, deb, moitie, fin); // Fusion des deux moitiés triées.
}
}
// Fonction pour fusionner deux séquences triées dans un tableau d'arêtes.
// Les séquences sont [deb, fin1] et [fin1 + 1, fin].
// Paramètres :
// - tab : tableau d'arêtes contenant les séquences à fusionner.
// - deb : indice de début de la première séquence à fusionner.
// - fin1 : indice de fin de la première séquence (et donc début de la seconde - 1).
// - fin : indice de fin de la seconde séquence à fusionner.
// Fonction fusion
void fusion(Noeud* tab, int deb, int fin1, int fin)
{
Noeud* temp = (Noeud*)malloc((fin - deb + 1) * sizeof(Noeud)); // Allocation d'un tableau temporaire pour la fusion.
int i1 = deb, i2 = fin1 + 1, itemp = 0; // Initialisation des indices pour la fusion.
// Tant qu'il reste des éléments dans l'une ou l'autre séquence.
while (i1 <= fin1 || i2 <= fin) {
// Si la deuxième séquence est terminée ou si l'élément de la première séquence est plus petit.
if (i2 > fin || (i1 <= fin1 && tab[i1].poids <= tab[i2].poids)) {
temp[itemp++] = tab[i1++]; // On ajoute l'élément de la première séquence au tableau temporaire.
} else {
temp[itemp++] = tab[i2++]; // Sinon, on ajoute l'élément de la deuxième séquence.
}
}
// Copie du tableau temporaire trié dans la partie correspondante du tableau original.
for (int i = deb; i <= fin; i++) {
tab[i] = temp[i - deb];
}
free(temp); // Libération de la mémoire allouée pour le tableau temporaire.
}
//---------------------------------------------- Liste Djikistra+ Prim------------------------------------------------------
// Fonction qui initialise la liste
void initialiser_liste(Liste *liste)
{
liste->tete = NULL; // Initialise la tête de la liste à NULL, indiquant que la liste est vide.
}
// Fonction qui ajoute en tete de liste
void ajouter_en_tete_de_liste(Liste *liste, int identifiant)
{
Element *nouvel_element = (Element *)malloc(sizeof(Element)); // Alloue de la mémoire pour un nouvel élément de la liste.
nouvel_element->id = identifiant; // Affecte l'identifiant au nouvel élément.
nouvel_element->suivant = liste->tete; // Le nouvel élément pointe vers l'ancienne tête de la liste.
liste->tete = nouvel_element; // Met à jour la tête de la liste pour qu'elle pointe vers le nouvel élément.
}
//Fonction qui vérifie si la liste est vide
bool est_vide(Liste *liste)
{
return liste->tete == NULL; // Retourne vrai si la tête de la liste est NULL, indiquant que la liste est vide.
}
//Fonction qui supprime un élément d'une liste en fonction de son identifiant
void supprimer_element(Liste *liste, int id_element)
{
if (liste->tete != NULL) // Vérifie si la liste n'est pas vide.
{
Element *courant, *precedent;
precedent = NULL;
courant = liste->tete;
while (courant != NULL && courant->id != id_element) // Parcourt la liste jusqu'à trouver l'élément ou atteindre la fin.
{
precedent = courant;
courant = courant->suivant; // Déplacement correct de courant au prochain élément.
}
if (courant != NULL) // Si l'élément a été trouvé (courant n'est pas NULL).
{
if (precedent != NULL) // Si l'élément n'est pas la tête de la liste.
{
precedent->suivant = courant->suivant; // Retire l'élément de la chaîne.
}
else // Si l'élément à supprimer est la tête de la liste.
{
liste->tete = courant->suivant; // Met à jour la tête de la liste.
}
free(courant); // Libère la mémoire allouée pour l'élément supprimé.
}
}
}
// Fonction qui affiche la liste
void affiche_liste(Liste *liste)
{
Element *element = liste->tete; // Initialise 'element' au premier élément de la liste pour commencer le parcours.
printf("Liste : "); // Affiche un préambule pour indiquer le début de l'impression de la liste.
while (element != NULL) // Boucle tant qu'il existe un élément à traiter (fin de liste non atteinte).
{
printf("%d ", element->id); // Affiche l'identifiant de l'élément courant.
element = element->suivant; // Passe à l'élément suivant de la liste.
}
printf("\n"); // Imprime une nouvelle ligne après avoir listé tous les éléments.
}
// Fonction qui obtient l'id de tete
int obtenir_id_tete(Liste *liste)
{
if (liste->tete == NULL) // Si la liste est vide, retourne 0.
return 0;
else
return liste->tete->id; // Sinon, retourne l'identifiant de l'élément en tête de liste.
}
// Fonction qui supprime la tête d'une liste
void supprimer_tete(Liste *liste)
{
if (liste->tete != NULL) // Vérifie si la liste n'est pas vide.
{
Element *ancienne_tete = liste->tete; // Sauvegarde l'ancienne tête de la liste.
liste->tete = liste->tete->suivant; // Avance la tête de la liste au prochain élément.
free(ancienne_tete); // Libère la mémoire allouée à l'ancienne tête.
}
}
//Fonction qui libère tous les éléments de la liste
void liberer_liste(Liste *liste)
{
while (liste->tete != NULL)// Tant que la liste n'est pas vide,
{
supprimer_tete(liste); // Supprime l'élément en tête de liste.
}
}
// Fonction qui vérifie si un élément est dans la liste en fonction de son id
bool est_dans_liste(Liste* liste, int id_element)
{
Element* courant = liste->tete; // Initialise un pointeur `courant` pour parcourir la liste, en commençant par la tête de la liste.
while (courant != NULL)// Démarre une boucle qui continue tant que `courant` n'est pas NULL, signifiant qu'on n'a pas atteint la fin de la liste.
{
if (courant->id == id_element) // Vérifie si l'identifiant de l'élément courant correspond à `id_element`.
{
return true;// Si oui, retourne `true`, indiquant que l'élément est présent dans la liste.
}
courant = courant->suivant; // Si l'élément courant n'est pas celui recherché, met à jour `courant` pour passer à l'élément suivant dans la liste.
}
return false;// Si la boucle se termine sans trouver l'élément, retourne `false`, indiquant que l'élément n'est pas dans la liste.
}
// Fonction qui donne l'indice de l'élément avec la distance minimale
int obtenir_indice_min_dans_liste(int* distances, Liste *liste) {
if (liste->tete == NULL) { // Si la liste est vide, retourne -1 ou un autre indicateur d'erreur.
return -1;
}
int min = distances[liste->tete->id]; // Initialise le minimum avec la distance du premier élément de la liste.
int indice_min = liste->tete->id; // L'indice de l'élément avec la distance minimale commence par l'ID de la tête de la liste.
Element *courant = liste->tete->suivant; // Commence avec le deuxième élément de la liste.
while(courant != NULL) { // Parcourt la liste jusqu'à la fin.
if (min > distances[courant->id]) { // Si la distance actuelle est inférieure au minimum actuel.
min = distances[courant->id]; // Met à jour la valeur minimale.
indice_min = courant->id; // Met à jour l'indice de l'élément avec la valeur minimale.
}
courant = courant->suivant; // Passe à l'élément suivant de la liste.
}
return indice_min; // Retourne l'indice de l'élément avec la distance minimale.
}
//-----------------------------------------Tas de Prim--------------------------------------------------------
// Fonction qui creer un tas vide avec une taille maximale donnée
void creer_tas_vide(Tas *tas, int taille_max)
{
tas->tableau = (ElementTas*) malloc(taille_max * sizeof(ElementTas)); // Alloue de la mémoire pour le tableau d'éléments du tas
tas->taille = 0; // Initialise la taille du tas à 0, signifiant qu'il est vide
}
// Fonction qui cree un tas à partir d'un tableau d'elements existants
void creer_tas(Tas *tas, ElementTas *tableau_elements, int taille_reelle, int taille_max)
{
creer_tas_vide(tas, taille_max); // Initialise d'abord le tas comme vide avec la taille maximale spécifiée
for (int i = 0; i < taille_reelle; i++) // Pour chaque élément jusqu'à la taille réelle
inserer_dans_tas(tas, tableau_elements[i]); // Insère chaque élément dans le tas
}
// Fonction qui calcule et retourne l'indice du fils gauche d'un élément dans le tas, basé sur l'indice de cet élément
int indice_fils_gauche(int indice_cellule)
{
return 2 * indice_cellule + 1; // Formule pour trouver l'indice du fils gauche dans un tas binaire
}
// Fonction qui calcule et retourne l'indice du fils droit
int indice_fils_droit(int indice_cellule)
{
return 2 * indice_cellule + 2; // Formule pour trouver l'indice du fils droit dans un tas binaire
}
// Fonction qui calcule et retourne l'indice du parent d'un élément
int indice_parent(int indice_cellule)
{
return (indice_cellule - 1) / 2; // Formule pour trouver l'indice du parent dans un tas binaire
}
// Fonction qui calcule le nombre d'enfants
int nb_enfants(Tas *tas, int indiceCellule)
{
int nbDescendants;// Déclare une variable pour compter le nombre de descendants
if (indice_fils_gauche(indiceCellule) > tas->taille - 1) // Vérifie si l'indice du fils gauche est hors du tableau (pas de fils gauche)
nbDescendants = 0; // Aucun descendant
else if (indice_fils_droit(indiceCellule) > tas->taille - 1)// Sinon, vérifie si l'indice du fils droit est hors du tableau (un seul fils, le gauche)
nbDescendants = 1; // Un descendant (fils gauche uniquement)
else // Sinon, cela signifie qu'il y a deux descendants (fils gauche et droit)
nbDescendants = 2;
return nbDescendants;// Retourne le nombre de descendants
}
// Fonction qui donne l'élement qui se situe à l'indice du fils gauche
ElementTas enfant_gauche(Tas *tas, int indiceCellule)
{
return tas->tableau[indice_fils_gauche(indiceCellule)];// Retourne l'élément situé à l'indice du fils gauche dans le tableau du tas
}
// Fonction qui donne l'élement qui se situe à l'indice du fils droit
ElementTas enfant_droit(Tas *tas, int indiceCellule)
{
return tas->tableau[indice_fils_droit(indiceCellule)];// Retourne l'élément situé à l'indice du fils droit dans le tableau du tas
}
// Fonction qui recupère le contenu d'une cellule d'un tas
ElementTas contenu_cellule(Tas *tas, int indiceCellule)
{
return tas->tableau[indiceCellule];// Retourne l'élément situé à l'indiceCellule dans le tableau représentant le tas
}
// Fonction qui verifie si un element est dans le tas grâce à son identifiant
bool est_dans_tas(Tas *tas, int id)// Définit une fonction pour vérifier si un id est présent dans le tas.
{
bool trouveElement = false; // Initialise un booléen à faux pour suivre si l'id a été trouvé.
int i = 0; // Initialise un compteur à 0 pour parcourir les éléments du tas.
while (!trouveElement && i < tas->taille)// Boucle tant que l'élément n'est pas trouvé et que la fin du tas n'est pas atteinte.
{
if (tas->tableau[i].id == id) // Vérifie si l'id de l'élément actuel correspond à l'id recherché.
trouveElement = true; // Si correspondance, met à jour trouveElement à vrai et arrête la recherche.
else
i++; // Sinon, incrémente le compteur pour passer à l'élément suivant.
}
return trouveElement; // Retourne le booléen trouveElement, indiquant si l'id est présent dans le tas ou non.
}
// Fonction qui trouve l'indice d'un élément dans le tas
int obtenir_indice_dans_tas(Tas *tas, ElementTas element)
{
bool trouveElement = false;
int i = 0;
while (!trouveElement && i < tas->taille)
{
if (tas->tableau[i].id == element.id)
trouveElement = true;
else
i++;
}
return i;
}
// Fonction qui échange un élément avec son parent
void echanger_avec_parent(Tas *tas, int indiceCellule)
{
ElementTas element = contenu_cellule(tas, indiceCellule); // Obtient l'élément à l'indice spécifié
int indiceParent = indice_parent(indiceCellule); // Calcule l'indice du parent de l'élément
// Effectue l'échange
tas->tableau[indiceCellule] = tas->tableau[indiceParent];
tas->tableau[indiceParent] = element;
}
// Fonction qui affiche un tas
void affiche_tas(Tas *tas)
{
int i, niveau = 0, nbDescendants; // Déclare les indices de boucle, le niveau actuel dans l'arbre et le nombre de descendants
for (i = 0; i < tas->taille; i++) // Itère sur chaque élément du tas
{
printf("%d", contenu_cellule(tas, i).id); // Affiche l'ID de l'élément courant
nbDescendants = nb_enfants(tas, i); // Calcule le nombre de descendants (enfants) de l'élément courant
if (nbDescendants == 2) // Si l'élément a deux enfants
printf("(%d %d)", enfant_gauche(tas, i).id, enfant_droit(tas, i).id); // Affiche les IDs des enfants gauche et droit
else if (nbDescendants == 1) // Si l'élément a un seul enfant (gauche)
printf("(%d)", enfant_gauche(tas, i).id); // Affiche l'ID de l'enfant gauche
if ((i + 1) == (1 << (niveau + 1)) - 1) // Calcule si le prochain élément démarre un nouveau niveau dans la représentation de l'arbre
{
printf("\n"); // Affiche un saut de ligne pour séparer les niveaux de l'arbre
niveau++; // Incrémente le niveau pour le prochain cycle de la boucle
} else
{
printf(" "); // Affiche un espace pour séparer les éléments du même niveau
}
}
printf("\n"); // Affiche un saut de ligne à la fin de l'impression du tas
}
//Objectif : Restaurer les propriétés du tas après l'ajout d'un nouvel élément.
//Comment ça fonctionne : Quand un nouvel élément est ajouté au tas, il est initialement placé à la fin. La fonction remonter compare cet élément à son parent et, si les propriétés du tas ne sont pas respectées (par exemple, l'élément est plus petit que son parent dans un tas min), ils sont échangés. Ce processus se répète jusqu'à ce que l'élément soit correctement placé, soit parce qu'il n'a plus de parent (il est devenu la racine du tas), soit parce que le parent respecte la propriété du tas par rapport à cet élément.
//Utilisation : Principalement après l'insertion d'un nouvel élément dans le tas.
//Fonction descendre (heapify_down)
//Objectif : Rétablir les propriétés du tas après la suppression de l'élément racine.
//Comment ça fonctionne : Lorsque l'élément racine est retiré d'un tas, l'élément le plus à droite du dernier niveau est temporairement déplacé à la racine pour maintenir une structure complète. La fonction descendre s'assure que la nouvelle racine est déplacée vers le bas du tas jusqu'à ce qu'elle se trouve à une position qui respecte les propriétés du tas. Cela est réalisé en échangeant répétitivement cet élément avec son enfant le plus petit (dans un tas min) ou le plus grand (dans un tas max), jusqu'à ce que l'élément soit à sa place correcte.
//Utilisation : Après la suppression de l'élément racine du tas ou lors de la construction d'un tas à partir d'un tableau non organisé.
// Fonction qui remonte l'element à la bonne place quand il ets inséré
void remonter(Tas *tas, int indiceElement) {
bool bienPlace = false; // Initialise un indicateur pour suivre si l'élément est correctement placé
if (tas->taille == 1)
bienPlace = true; // Si le tas contient un seul élément, il est déjà bien placé
while (!bienPlace) // Continue tant que l'élément n'est pas bien placé
{
int indiceParent = indice_parent(indiceElement); // Calcule l'indice du parent de l'élément
if (indiceParent < 0 || tas->tableau[indiceParent].valeur <= tas->tableau[indiceElement].valeur)
bienPlace = true; // Si l'élément est à la racine ou respecte la propriété du tas, il est bien placé
else
{
echanger_avec_parent(tas, indiceElement); // Sinon, échange l'élément avec son parent
indiceElement = indiceParent; // Met à jour l'indice pour refléter la nouvelle position de l'élément
}
}
}
// Fonction qui remet un élement à sa place quand on retire un element du tas cf explication en haut
void descendre(Tas *tas, int indiceElement)
{
int indicePlusPetit = indiceElement; // Commence par supposer que l'élément est au bon endroit
int indiceGauche = indice_fils_gauche(indiceElement); // Calcule l'indice du fils gauche
int indiceDroit = indice_fils_droit(indiceElement); // Calcule l'indice du fils droit
// Vérifie si le fils gauche existe et est plus petit que l'élément
if (indiceGauche < tas->taille && tas->tableau[indiceGauche].valeur < tas->tableau[indiceElement].valeur)
indicePlusPetit = indiceGauche; // Met à jour l'indice du plus petit élément
// Vérifie si le fils droit existe et est plus petit que l'élément ou le fils gauche
if (indiceDroit < tas->taille && tas->tableau[indiceDroit].valeur < tas->tableau[indicePlusPetit].valeur)
indicePlusPetit = indiceDroit; // Met à jour l'indice du plus petit élément
// Si l'élément n'est pas à sa place correcte, échange avec le plus petit de ses enfants
if (indicePlusPetit != indiceElement)
{
ElementTas temp = tas->tableau[indiceElement]; // Temporairement stocke l'élément à déplacer
tas->tableau[indiceElement] = tas->tableau[indicePlusPetit]; // Remplace l'élément par son plus petit enfant
tas->tableau[indicePlusPetit] = temp; // Place l'élément original à la position du plus petit enfant
descendre(tas, indicePlusPetit); // Répète récursivement pour l'élément déplacé
}
}
// Fonction qui extrait l'élément minimal d'un tas min
ElementTas extraire_min(Tas *tas)
{
if (tas->taille == 0)
{
// Gérer l'erreur ou retourner une valeur par défaut si le tas est vide.
// Cela dépend de la manière dont vous souhaitez gérer ce cas.
ElementTas elementVide;
return elementVide; // Assurez-vous de définir un comportement approprié ici.
}
ElementTas min_element = tas->tableau[0]; // Sauvegarde l'élément minimal, qui est à la racine du tas.
// Remplace la racine par le dernier élément dans le tas.
tas->tableau[0] = tas->tableau[tas->taille - 1];
tas->taille--; // Réduit la taille du tas, effectivement supprimant le dernier élément.
// Restaure les propriétés du tas en descendant l'élément nouvellement placé à la racine vers sa position correcte.
descendre(tas, 0);
return min_element; // Retourne l'élément minimal.
}
//Fonction qui retoune l'element maximum du tas
ElementTas extraire_max(Tas *tas)
{
if (tas->taille == 0)
{
// Gérer l'erreur ou retourner une valeur par défaut si le tas est vide.
// Cela dépend de la manière dont vous souhaitez gérer ce cas.
ElementTas elementVide;
return elementVide; // Assurez-vous de définir un comportement approprié ici.
}
ElementTas max_element = tas->tableau[0]; // Sauvegarde l'élément maximal, qui est à la racine du tas.
tas->tableau[0] = tas->tableau[tas->taille - 1]; // Remplace la racine par le dernier élément dans le tas.
tas->taille--; // Réduit la taille du tas, effectivement supprimant le dernier élément.
// Restaure les propriétés du tas en descendant l'élément nouvellement placé à la racine vers sa position correcte.
descendre(tas, 0); // Assurez-vous que cette fonction est adaptée pour un tas max.
return max_element; // Retourne l'élément maximal.
}
// Fonction qui insère dans un tax
void inserer_dans_tas(Tas *tas, ElementTas nouvelElement)
{
// Ajoute le nouvel élément à la fin du tas
tas->tableau[tas->taille] = nouvelElement;
// Incrémente la taille du tas
tas->taille++;
// Maintenant, assurez-vous que les propriétés du tas sont toujours respectées
remonter(tas, tas->taille - 1);
}
// Fonction qui met un jour un tas après avoir inséré ou retirer un element
void mettre_a_jour_priorite(Tas *tas, ElementTas nouvelElement)
{
int indiceElement = obtenir_indice_dans_tas(tas, nouvelElement);
if (indiceElement == -1)
{
// L'élément n'est pas trouvé dans le tas.
return;
}
bool augmenterPriorite = (tas->tableau[indiceElement].valeur > nouvelElement.valeur); // Détermine si la mise à jour augmente la priorité de l'élément (true si la nouvelle valeur est inférieure à l'ancienne dans un tas min).
tas->tableau[indiceElement].valeur = nouvelElement.valeur; // Met à jour la valeur de l'élément dans le tas à la nouvelle valeur spécifiée.
if (augmenterPriorite)
{
descendre(tas, indiceElement); // Si la nouvelle priorité est plus faible, descendre l'élément dans le tas.
} else // Si la nouvelle priorité est plus élevée, remonter l'élément dans le tas.
{
remonter(tas, indiceElement);
}
}
//--------------------------------------Djikistra Graphe---------------------------------------------------
// Pour djikistra, on utilise cette fonction Cree_graphe_oriente_a_partir_de_fichier
// Fonction qui initialise djikistra
void dijkstra_initialiser(Graphe* G, int* tableau_distances, bool* tableau_visites, int source)
{
// Boucle qui parcourt tous les noeuds du graphe
for (int i = 0; i < G->nb_noeuds; i++)
{
tableau_distances[i] = INFINITY;// Initialise la distance de chaque noeud à l'infini.// Cela indique que la distance minimale de la source à ce noeud n'est pas encore connue.
tableau_visites[i] = false; // Marque chaque noeud comme non visité.
}
tableau_distances[source] = 0; // Initialise la distance de la source à elle-même à 0.
}
// Fonction qui fait djikistra sans tas
void dijkstra_sans_tas(Graphe* graphe, int source, int* tableau_distances) // le source,c'ets le noeud source
{
bool *tableau_visites = (bool*) malloc(graphe->nb_noeuds * sizeof(bool)); // Alloue un tableau pour suivre quels noeuds ont été visités.
dijkstra_initialiser(graphe, tableau_distances, tableau_visites, source); // Initialise les distances et les visites avec le noeud source.
Liste liste_traitement; // Crée une liste pour gérer les noeuds à traiter.
initialiser_liste(&liste_traitement); // Initialise la liste de traitement comme vide.
ajouter_en_tete_de_liste(&liste_traitement, source); // Ajoute le noeud source à la liste de traitement.
while(!est_vide(&liste_traitement)) // Continue tant que la liste de traitement n'est pas vide.
{
int noeud_actuel = obtenir_indice_min_dans_liste(tableau_distances, &liste_traitement); // Trouve le noeud avec la distance minimale dans la liste.
supprimer_element(&liste_traitement, noeud_actuel); // Supprime ce noeud de la liste de traitement.
Noeud* arc_sortant = graphe->liste_successeurs[noeud_actuel]; // Parcourt les arcs sortants du noeud actuel.
while(arc_sortant != NULL) // Continue tant qu'il y a des arcs sortants.
{
int noeud_destination = arc_sortant->id; // Identifie le noeud de destination de l'arc actuel.
// Si la distance actuelle plus le poids de l'arc est inférieure à la distance enregistrée pour le noeud de destination,
// met à jour cette distance.
if(tableau_distances[noeud_actuel] + arc_sortant->poids < tableau_distances[noeud_destination])
{
tableau_distances[noeud_destination] = tableau_distances[noeud_actuel] + arc_sortant->poids; // Met à jour la distance.
if (!tableau_visites[noeud_destination]) // Si le noeud de destination n'a pas encore été visité,
{
ajouter_en_tete_de_liste(&liste_traitement, noeud_destination); // l'ajoute à la liste de traitement.
tableau_visites[noeud_destination] = true; // Marque le noeud de destination comme visité.
}
}
arc_sortant = arc_sortant->successeur; // Passe à l'arc sortant suivant.
}
}
free(tableau_visites); // Libère la mémoire allouée pour le tableau de visites une fois terminé.
}
// Fonction qui fait dijkstra avec des tas
void dijkstra_avec_tas(Graphe* G, int source, int* tableau_distances)
{
bool *tableau_visites = (bool*) malloc(G->nb_noeuds * sizeof(bool)); // Alloue un tableau de booléens pour suivre quels nœuds ont été visités.
dijkstra_initialiser(G, tableau_distances, tableau_visites, source);// Initialise les distances et les visites avec le nœud source.
Tas tas_traitement; // Déclare un tas pour gérer les nœuds pendant l'exécution de l'algorithme.
creer_tas_vide(&tas_traitement, G->nb_noeuds); // Initialise le tas à vide avec une capacité maximale égale au nombre de nœuds du graphe.
ElementTas hsource = {source, 0}; // Crée un élément de tas pour le nœud source avec une priorité de 0.
inserer_dans_tas(&tas_traitement, hsource); // Insère l'élément source dans le tas.
while(tas_traitement.taille > 0) // Boucle tant que le tas n'est pas vide.
{
ElementTas element_extrait = extraire_min(&tas_traitement); // Extrait le nœud avec la plus petite distance (priorité) du tas.
int u = element_extrait.id; // Stocke l'identifiant du nœud extrait.
Noeud* arc_sortant = G->liste_successeurs[u]; // Parcourt tous les arcs sortants du nœud u.
while(arc_sortant != NULL)
{
// Identifie le nœud de destination de l'arc actuel.
int v = arc_sortant->id;
if(tableau_distances[u] + arc_sortant->poids < tableau_distances[v]) // Si la distance actuelle au nœud u plus le poids de l'arc est inférieure à la distance connue au nœud v...
{
tableau_distances[v] = tableau_distances[u] + arc_sortant->poids;// Met à jour la distance au nœud v.
ElementTas hnode = {v, tableau_distances[v]};// Crée un nouvel élément de tas pour le nœud v avec sa nouvelle distance comme priorité.
if (!tableau_visites[v]) // Si le nœud v n'a pas encore été visité...
{
inserer_dans_tas(&tas_traitement, hnode); // Insère le nœud v dans le tas.
tableau_visites[v] = true;// Marque le nœud v comme visité.
}
else {
mettre_a_jour_priorite(&tas_traitement, hnode); // Si le nœud v a déjà été visité, met à jour sa priorité dans le tas.
}
}
// Passe à l'arc sortant suivant du nœud u.
arc_sortant = arc_sortant->successeur;
}
}
// Libère la mémoire allouée pour le tableau de visites.
free(tableau_visites);
}
//----------------------------------------Prim graphe avec Tas-----------------------------------------------
// Fonction qui initialise les tableaux pour l'algorithme de Prim sur un graphe G
void prim_initialiser(Graphe* G, int* tableau_distances, int* tableau_parents)
{
for (int i = 0; i < G->nb_noeuds; i++) // Parcourt tous les noeuds du graphe
{
tableau_distances[i] = INFINITY; // Initialise la distance à l'infini, indiquant que le noeud n'est pas encore atteint
tableau_parents[i] = -1;// Marque -1 comme parent pour indiquer qu'il n'y a pas encore de parent attribué
}
tableau_distances[0] = 0;// Définit la distance du premier noeud à 0 pour le choisir comme point de départ
tableau_parents[0] = 0;// Marque lui-même comme son propre parent pour indiquer le début de l'arbre couvrant minimal
}
// Fonction qui effectue l'algo de Prim
int prim(Graphe* G, int* tableau_distances, int* tableau_parents)
{
prim_initialiser(G, tableau_distances, tableau_parents);// Initialise l'algorithme de Prim en définissant les distances à INFINITY et les parents à -1, sauf pour le noeud de départ.
int poidsTotal = 0;// Initialise le poids total de l'arbre couvrant minimal à 0.
Tas tasTraitement;// Déclare un tas pour gérer les noeuds pendant l'exécution de l'algorithme.
creer_tas_vide(&tasTraitement, G->nb_noeuds); // Initialise le tas à vide avec une capacité maximale égale au nombre de noeuds dans le graphe.
ElementTas source = {0, 0};// Crée un élément de tas pour le noeud source (index 0) avec une priorité de 0 pour commencer l'algorithme.
inserer_dans_tas(&tasTraitement, source); // Insère le noeud source dans le tas.
for (int i = 1; i < G->nb_noeuds; i++) // Initialise tous les autres noeuds avec une priorité INFINITY dans le tas pour les traiter.
{
ElementTas element = {i, INFINITY};
inserer_dans_tas(&tasTraitement, element);
}
while(tasTraitement.taille > 0) // Continue tant que le tas n'est pas vide.
{
ElementTas extrait = extraire_min(&tasTraitement);// Extrait le noeud avec la plus petite priorité (distance) du tas.
int u = extrait.id;// Récupère l'ID du noeud extrait.
if (tableau_parents[u] != -1) // Met à jour le poids total de l'arbre couvrant minimal pour les noeuds autres que le noeud source.
{
poidsTotal += tableau_distances[u];
}
Noeud* arcSortant = G->liste_successeurs[u]; // Parcourt tous les arcs sortants du noeud extrait.
while(arcSortant != NULL) // Récupère l'ID du noeud de destination de l'arc sortant.
{
int v = arcSortant->id;
if (est_dans_tas(&tasTraitement, v) && arcSortant->poids < tableau_distances[v]) // Si le noeud de destination est encore dans le tas et que le poids de l'arc est inférieur à la distance connue...
{
tableau_distances[v] = arcSortant->poids; // Met à jour la distance du noeud de destination.
tableau_parents[v] = u;// Met à jour le parent du noeud de destination dans l'arbre couvrant minimal.
ElementTas noeud = {v, tableau_distances[v]}; // Crée un nouvel élément de tas avec la distance mise à jour et met à jour sa priorité dans le tas.
mettre_a_jour_priorite(&tasTraitement, noeud);
}
arcSortant = arcSortant->successeur; // Passe au successeur suivant dans la liste des arcs sortants.
}
}
return poidsTotal;// Retourne le poids total calculé de l'arbre couvrant minimal.
}
//----------------------------------------Prim graphe sans tas-----------------------------------------------
void prim_sans_tas(Graphe* G, int* tableau_distances, int* tableau_parents)
{
Liste listeNoeudsRestants; // Déclare une liste pour stocker les noeuds qui ne font pas encore partie de l'arbre couvrant minimal.
initialiser_liste(&listeNoeudsRestants); // Initialise cette liste, la rendant prête à stocker des noeuds.
for (int i = 1; i < G->nb_noeuds; i++) // Remplit la liste avec tous les noeuds sauf le premier et initialise les tableaux de distances et de parents.
{
ajouter_en_tete_de_liste(&listeNoeudsRestants, i); // Ajoute chaque noeud à la liste des noeuds restants.
tableau_distances[i] = INFINITY; // Initialise la distance à l'infini pour indiquer qu'ils sont initialement inaccessibles.
tableau_parents[i] = -1; // Initialise le parent à -1 pour indiquer qu'ils n'ont pas encore de parent dans l'arbre.
}
tableau_distances[0] = 0; // La distance du premier noeud à lui-même est 0.
tableau_parents[0] = 0; // Le premier noeud est son propre parent pour démarrer l'algorithme.
while (!est_vide(&listeNoeudsRestants)) // Tant qu'il reste des noeuds à traiter, continue l'exécution.
{
int noeudMin = obtenir_indice_min_dans_liste(tableau_distances, &listeNoeudsRestants);// Sélectionne le noeud avec la distance minimale parmi ceux restants.
supprimer_element(&listeNoeudsRestants, noeudMin); // Retire ce noeud de la liste des noeuds restants.
Noeud* courant = G->liste_successeurs[noeudMin]; // Parcourt les arcs sortants du noeud sélectionné.
while (courant != NULL)
{
int dest = courant->id; // Destination de l'arc courant.
int poids = courant->poids; // Poids de l'arc courant.
// Vérifie si le noeud destination est toujours dans la liste des noeuds restants.
if (est_vide(&listeNoeudsRestants) || !est_dans_liste(&listeNoeudsRestants, dest))
{
courant = courant->successeur; // Si non, passe au suivant.
continue;
}
if (tableau_distances[dest] > poids) // Si le poids de l'arc est inférieur à la distance actuelle du noeud destination, met à jour sa distance et son parent.
{
tableau_distances[dest] = poids;
tableau_parents[dest] = noeudMin;
}
courant = courant->successeur; // Passe au noeud successeur suivant.
}
}
}
//----------------------------------------Bellman-Ford ( liste d'adjacence)-----------------------------------------------
//L'algorithme de Bellman-Ford classique fonctionne avec des relaxations successives de toutes
//les arêtes du graphe et ne s'appuie pas sur une structure de tas pour sa mise en œuvre standard.
//L'usage de tas est typiquement associé à l'algorithme de Dijkstra pour trouver les chemins les plus
//courts dans les graphes sans cycles de poids négatif, car il permet d'extraire le nœud le plus proche
//(ou de priorité minimale) de manière efficace.
//Trouver le chemin le plus court : L'algorithme de Bellman-Ford est utilisé pour trouver le chemin le
//plus court du nœud source à tous les autres nœuds dans un graphe.
//Graphes avec poids négatifs : Contrairement à l'algorithme de Dijkstra, Bellman-Ford peut gérer
//les graphes contenant des arêtes avec des poids négatifs, tout en garantissant de trouver le chemin le plus court si le graphe ne contient pas de cycle de poids négatif.
//Détection de cycles de poids négatif : Bellman-Ford peut détecter l'existence de cycles
//de poids négatif dans le graphe, ce qui est crucial dans certaines applications comme l'optimisation
//de réseau ou la vérification de la cohérence des systèmes de contraintes.
bool bellman_ford(Graphe* G, int source, int* tableau_distances)
{
for (int i = 0; i < G->nb_noeuds; i++)// Initialise toutes les distances à INFINITY, sauf la source à 0.
tableau_distances[i] = INFINITY; // Initialise la distance pour chaque noeud à INFINITY.
tableau_distances[source] = 0; // Initialise la distance de la source à elle-même à 0.
for (int i = 0; i < G->nb_noeuds - 1; i++) // Effectue la relaxation pour chaque arête (nb_noeuds - 1 fois).
{ // Répète le processus nb_noeuds - 1 fois.
for (int u = 0; u < G->nb_noeuds; u++) // Pour chaque noeud u dans le graphe...
{
Noeud* arc_sortant = G->liste_successeurs[u]; // Accède à la liste des arcs sortants de u.
while (arc_sortant != NULL)// Pour chaque arc sortant de u...
{
int v = arc_sortant->id; // Obtient l'ID du noeud de destination v de l'arc.
// Si la distance actuelle à u plus le poids de l'arc est inférieure à la distance actuelle à v, met à jour la distance à v.
if (tableau_distances[u] + arc_sortant->poids < tableau_distances[v])
{
tableau_distances[v] = tableau_distances[u] + arc_sortant->poids; // Mise à jour de la distance à v.
}
arc_sortant = arc_sortant->successeur; // Passe à l'arc sortant suivant.
}
}
}
// Vérifie l'existence de cycles de poids négatif.
for (int u = 0; u < G->nb_noeuds; u++) // Pour chaque noeud u dans le graphe...
{
Noeud* arc_sortant = G->liste_successeurs[u]; // Accède à la liste des arcs sortants de u.
while (arc_sortant != NULL)// Pour chaque arc sortant de u...
{
if (tableau_distances[u] + arc_sortant->poids < tableau_distances[arc_sortant->id])// Si la distance à u plus le poids de l'arc est toujours inférieure à la distance à v, il y a un cycle de poids négatif.
return false; // Retourne false indiquant la présence d'un cycle de poids négatif.
arc_sortant = arc_sortant->successeur; // Passe à l'arc sortant suivant.
}
}
return true; // Retourne true si aucun cycle de poids négatif n'a été détecté.
}
//--------------------------------------Kuruska Graphe ACM---------------------------------------------------
//----------------------------------------Menu -----------------------------------------------
int main()
{
const char* nomFichierGraphe = "graph_10_13_weighted.txt"; // Assurez-vous que ce fichier existe et est correctement formaté
Graphe G;
// Assumant que vous avez une fonction pour créer un graphe à partir d'un fichier, je vais ajuster le nom pour correspondre à votre code
Cree_graphe_oriente_a_partir_de_fichier(&G, nomFichierGraphe);
printf("Graphe G (Liste d'adjacence) : \n");
afficher_graphe(&G);
int* tableau_distances = (int*) malloc(G.nb_noeuds * sizeof(int));
int* tableau_parents = (int*) malloc(G.nb_noeuds * sizeof(int));
// Appel de votre fonction prim adaptée
int poidsTotal = prim(&G, tableau_distances, tableau_parents);
printf("Poids de l'arbre couvrant minimal (%s) : %d\n\n", nomFichierGraphe, poidsTotal);
printf("Arêtes dans l'arbre couvrant :\n\n");
for(int i = 0; i < G.nb_noeuds; i++) {
// Notez que pour un affichage correct, vous devrez gérer les cas où parent_array[i] est -1 (pour la racine de l'arbre par exemple)
if (tableau_parents[i] != -1) // Si ce n'est pas la racine
printf("%d -- %d avec poids %d\n", i + 1, tableau_parents[i] + 1, tableau_distances[i]);
else
printf("%d est la racine de l'arbre\n", i + 1);
}
printf("\n \n");
free(tableau_distances);
free(tableau_parents);
return 0;
}
To embed this project on your website, copy the following code and paste it into your website's HTML: