Tri topologique (DFS)

Un tri topologique d'un graphe orienté acyclique (DAG) consiste à ordonner ses sommets de telle sorte que pour chaque arc u -> v, le sommet u apparaisse avant le sommet v dans la liste. Nous allons implémenter ce tri à l'aide d'un parcours en profondeur (DFS).

Le graphe est représenté par une liste d'adjacence via un tableau de listes (int list array). Pour suivre l'état de chaque sommet lors de l'exploration, nous utiliserons le type suivant (déjà fourni) : type etat_sommet = A_Explorer | En_Exploration | Explore;;

1. 1

   Indice

   Utilisez Array.make et Array.length pour créer le tableau à la bonne dimension.

   Initialisation des états : Écrire une fonction initialiser_etats : 'a array -> etat_sommet array qui prend un graphe en paramètre et renvoie un tableau de même taille, initialisé entièrement avec l'état A_Explorer. Par exemple, initialiser_etats [| [1]; [] |] renvoie [| A_Explorer; A_Explorer |].

2. 2

   Indice

   N'oubliez pas d'utiliser l'opérateur ! pour lire la valeur de la référence et l'opérateur := pour la modifier.

   Ajout en tête : Écrire une fonction ajouter_en_tete : 'a list ref -> 'a -> unit qui ajoute un élément au début d'une liste modifiable (référence). Par exemple, let l = ref [2] in ajouter_en_tete l 1; !l renvoie [1; 2].

3. 3

   Indice

   Utilisez List.iter pour parcourir simplement les voisins du sommet courant, et une structure de filtrage par motif (match ... with) pour traiter les 3 états possibles du sommet.

   Exploration d'un sommet : Écrire une fonction récursive explorer : int list array -> etat_sommet array -> int list ref -> int -> unit. Cette fonction prend le graphe, le tableau des états, la référence contenant l'ordre topologique, et le sommet s à explorer.

   • Si l'état de s est Explore, la fonction ne fait rien.
   • S'il est En_Exploration, le graphe contient un cycle : déclenchez une erreur avec failwith "CYCLE DETECTE".
   • S'il est A_Explorer, marquez-le En_Exploration, explorez récursivement tous ses voisins, marquez-le Explore, puis ajoutez-le en tête de l'ordre topologique à l'aide de la fonction précédente. Par exemple, let g = [| [1]; [] |] in let etats = [| A_Explorer; A_Explorer |] in let ordre = ref [] in explorer g etats ordre 0; !ordre modifie l'état de 0 et 1 et renvoie [0; 1].
4. 4

   Indice

   Utilisez une boucle for pour itérer sur tous les sommets du graphe de 0 à n-1.

   Tri topologique complet : Écrire une fonction trier_topologiquement : int list array -> int list qui initialise le tableau d'états, crée une liste d'ordre vide (via une référence), puis parcourt tous les sommets du graphe de 0 à n-1. Si un sommet est A_Explorer, elle appelle la fonction explorer. Enfin, elle renvoie la liste contenant l'ordre topologique. Par exemple, let g = [| [1; 2]; [2]; [] |] in trier_topologiquement g renvoie [0; 1; 2].