Algorithme de Prim

L'objectif de l'exercice est de mettre en œuvre l'algorithme de Prim pour calculer un arbre recouvrant minimal d'un graphe connexe pondéré non orienté, représenté par une liste d'adjacence.

On définit les types algébriques suivants pour modélier un sommet, un graphe, une arête et une liste d'arêtes (qui pourrait être un arbre).

type sommet = int
type arete = { u : sommet; v : sommet; poids : int }
type graphe = (sommet * int) list array
type arbre = arete list

1. 1

   Indice

   Parcourir récursivement la liste d'arêtes en prenant le maximum des indices u et v de chaque arête.

   Écrire une fonction s_ind_max : arete list -> int qui renvoie l'indice maximal d'un sommet apparaissant dans la liste d'arêtes. Par exemple s_ind_max [{u=1; v=2; poids=1}; {u=0; v=3; poids=5}; {u=0; v=1; poids=3}] renvoie 3. On fait ici l'hypothèse que tous les sommets possèdent au moins un arête, ce qui est le cas dans un graphe connexe.

2. 2

   Indice

   Invoquer s_ind_max sur la liste d'arêtes puis ajouter 1 au résultat obtenu.

   En déduire une fonction nb_sommets : arete list -> int qui calcule le nombre de sommets d'un graphe connexe (sommets numérotés de 0 à n-1) à partir de sa liste d'arêtes. Par exemple nb_sommets [{u=1; v=2; poids=1}; {u=0; v=3; poids=5}; {u=0; v=1; poids=3}] renvoie 4.

3. 3

   Indice

   Allouer un tableau de listes vides de taille n puis insérer symétriquement chaque voisin dans les deux listes d'adjacence correspondantes.

   Écrire une fonction construire_graphe : arete list -> graphe qui construit la liste d'adjacence symétrique d'un graphe non orienté à partir d'une liste d'arêtes. Par exemple construire_graphe [{u=1; v=2; poids=1}; {u=0; v=1; poids=21}; {u=0; v=2; poids=3}] renvoie un tableau de taille 3 où g.(0) contient [(1; 21); (2; 3)] et g.(1) contient [(2; 1); (0; 21)].

4. 4

   Indice

   Parcourer la liste d'adjacence du sommet s en sautant les voisins déjà visités et en conservant l'arête de poids minimal rencontré.

   Écrire une fonction min_arete_frontiere : graphe -> bool array -> sommet -> arete option qui renvoie l'arête de poids minimal reliant le sommet s (déjà visité) à un sommet non encore visité (marqué false dans visites), ou None si tous les voisins sont déjà visités. Par exemple, pour un graphe à 3 sommets avec arêtes (0,1,20), (0,2,3), (1,2,30), min_arete_frontiere g [|true; false; false|] 0 renvoie Some {u=0; v=2; poids=3}.

5. 5

   Indice

   Appeler min_arete_frontiere, marquer le nouveau sommet dans le tableau de visites, puis retourner la paire (nouveau_sommet, arête).

   Écrire une fonction etape_prim : graphe -> bool array -> (sommet * arete) option qui effectue une étape élémentaire de Prim : elle trouve l'arête minimale de toute la frontière, marque le nouveau sommet comme visité dans visites, et renvoie la paire (nouveau_sommet, arete), ou None si le graphe est entièrement couvert.

6. 6

   Indice

   Initialiser un tableau de visites et un compteur, puis itérer avec une boucle while en appelant etape_prim jusqu'à ce que le compteur atteigne n.

   Écrire une fonction prim : graphe -> sommet -> arbre qui calcule l'arbre recouvrant minimal du graphe g en partant du sommet depart, en itérant jusqu'à ce que tous les sommets soient visités. Par exemple, sur le graphe à 5 sommets avec arêtes (0,1,20), (0,3,60), (1,2,30), (1,3,80), (1,4,100), (2,4,70), (3,4,90), prim g 0 renvoie une liste de 4 arêtes dont le poids total est minimal.

7. 7

   Indice

   Parcourer récursivement la liste d'arêtes en accumulant la somme des poids dans un paramètre d'accumulateur.

   Écrire une fonction total_poids : arbre -> int qui calcule la somme des poids des arêtes de l'arbre.

8. 8

   Indice

   Vérifier que la liste contient exactement n-1 arêtes puis marquer dans un tableau booléen tous les sommets apparaissant et tester que tous sont atteints.

   Écrire une fonction est_arbre_recouvrant : graphe -> arbre -> bool qui vérifie que l'arbre possède exactement n-1 arêtes (où n est le nombre de sommets du graphe) et que tous les sommets du graphe apparaissent dans au moins une arête de l'arbre. Par exemple est_arbre_recouvrant g (prim g 0) renvoie true pour un graphe connexe.