Algorithme de Kruskal

L'algorithme de Kruskal permet de trouver l'arbre recouvrant de poids minimum dans un graphe connexe non orienté et pondéré. Cet exercice vous guide dans l'implémentation de la structure de données Unir-Trouver ou Union-Find nécessaire pour détecter les cycles efficacement, puis dans l'écriture de l'algorithme de Kruskal sous deux formes différentes.

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
type union_find = { parent : int array; rang : int array }

Le module FilePriorite ne sera utilisé qu'à la dernière question.

1. 1

   Indice

   Utilise Array.init pour initialiser le tableau des parents et Array.make pour celui des rangs.
   Initialiser l'Union-Find : écrire une fonction initialiser_uf : int -> union_find qui crée et renvoie une structure Union-Find pour n éléments. Chaque élément est initialement son propre parent et son rang est 0. Exemple d'utilisation : let uf = initialiser_uf 3 in (uf.parent.(0), uf.rang.(0)) renvoie (0,0).
2. 2

   Indice

   Pense à la compression de chemin en mettant à jour le parent de 'x' avec le résultat de l'appel récursif.
   Trouver avec compression de chemin : écrire une fonction récursive trouver_uf : union_find -> int -> int qui renvoie le représentant de l'ensemble contenant x, tout en effectuant la compression de chemin pour aplatir l'arbre.
3. 3

   Indice

   Compare les rangs des racines. Attache l'arbre le moins profond sous l'arbre le plus profond.
   Unir par rang : écrire une fonction unir_uf : union_find -> int -> int -> unit qui fusionne les ensembles contenant x et y. L'arbre avec le rang le plus faible doit être attaché à la racine de l'autre. Si les rangs sont égaux, on choisit arbitrairement une racine et on incrémente son rang.
4. 4

   Indice

   Parcours la liste d'adjacence en mémorisant l'indice du sommet courant. Pour éviter les doublons (graphe non orienté), ne conserve que les arêtes (u, v, w) où u < v.
   Lister les arêtes : écrire une fonction lister_aretes : (int * int) list list -> (int * int * int) list qui transforme le graphe en une liste de triplets (source, destination, poids). Pour ne pas avoir de doublons, on ne gardera que les arêtes où source < destination. Exemple d'utilisation : let g = [[(1, 10)]; [(0, 10)]] in lister_aretes g renvoie [(0, 1, 10)].
5. 5

   Indice

   Utilise List.sort pour trier toutes les arêtes, puis parcours cette liste en utilisant tes fonctions trouver_uf et unir_uf.
   Prim (version tri) : écrire une fonction kruskal_tri_liste : (int * int) list list -> (int * int * int) list qui implémente l'algorithme de Kruskal en triant préalablement la liste complète des arêtes par ordre croissant de poids. Exemple d'utilisation : let g = [[(1, 10); (2, 5)]; [(0, 10); (2, 1)]; [(0, 5); (1, 1)]] in prim_tri_liste g renvoie l'arbre couvrant formé des arêtes de poids 1 et 5.
6. 6

   Indice

   Insère d'abord toutes les arêtes dans la file. Extraits le minimum itérativement tant que l'arbre n'a pas n-1 arêtes et que la file n'est pas vide.
   Prim (version file de priorité) : écrire une fonction kruskal_file : (int * int) list list -> (int * int * int) list qui implémente Kruskal en utilisant le module FilePriorite fourni, pour extraire au fur et à mesure l'arête de poids le plus faible au lieu de trier toute la liste d'un coup. Exemple d'utilisation : let g = [[(1, 10); (2, 5)]; [(0, 10); (2, 1)]; [(0, 5); (1, 1)]] in prim_file g renvoie un résultat équivalent à la question précédente.