Corrigé CCINP 2025 Informatique MP — Partie III (1) (Q10 à Q17) : Graphes pondérés en OCaml et composantes connexes

Le sujet rappelle Array.make, Array.length, a.(i), a.(i) <- e, List.iter, la boucle for (bornes incluses) et les fonctions max et min : 'a -> 'a -> 'a.

Q10. Écrire max_tab : int array -> int, qui renvoie le plus grand élément d'un tableau non vide, en temps linéaire justifié.

Un graphe pondéré de sommets $[[0,n-1]]$ ($n⩾1$) est représenté par listes d'adjacence pondérées : g.(i) contient les couples $(j,p(\{i,j\}))$ pour les voisins $j$ de $i$, chaque arête figurant dans les listes de ses deux extrémités, avec le même poids.

type graphe = (int * float) list array

let nb_sommets g = Array.length g

Sur le graphe de la figure 2 ci-dessous, g.(0) vaut par exemple [(2, 24.0); (6, 21.0); (7, 18.0); (8, 6.0)].

Q11. Donner une valeur possible de g.(7).

Une arête est représentée une seule fois, par le triplet $(w,i,j)$ avec $w=p(\{i,j\})$ et $i<j$. Les poids étant distincts, l'ordre < d'OCaml (lexicographique) compare deux arêtes selon leurs poids.

Q12. Écrire ajoute_arete : graphe -> (float * int * int) -> unit (arête absente au départ), en temps constant.
Q13. Écrire toutes_les_aretes : graphe -> (float * int * int) list, en $O(|S|+|A|)$ justifié.
Q14. Écrire récursivement min_arete : (float * int * int) list -> (float * int * int) (liste non vide) ; complexité ?

Composantes connexes : on veut un tableau c de taille $n$ où c.(i) est l'indice, entre $0$ et (nombre de composantes) $-1$, de la composante de $i$, la valeur $-1$ signifiant « pas encore déterminée » ; un sommet est visité si et seulement si c.(i) >= 0. Le sujet donne :

let rec explorer g c k s =
  if c.(s) < 0 then begin
    c.(s) <- k;
    List.iter (fun (v, _) -> explorer g c k v) g.(s)
  end

Q15. Décrire précisément l'effet de explorer g c k s.
Q16. Écrire composantes_connexes : graphe -> int array, en $O(|S|+|A|)$.
Q17. En déduire est_connexe : graphe -> bool.