Voisins communs

Exercice · OCaml (option informatique), chapitre 14 — Graphes : modélisation et représentations

Énoncé

Écrire voisins_communs m i j : le nombre de sommets voisins à la fois de i et de j.

Corrigé

let voisins_communs m i j =
  let n = Array.length m in
  let c = ref 0 in
  for k = 0 to n - 1 do
    if m.(i).(k) && m.(j).(k) then c := !c + 1
  done;
  !c

On compte les sommets k adjacents simultanément à i et à j. La matrice rend ce test direct ( $Θ (1)$ par sommet), d'où un coût $Θ (n)$ . (En listes, il faudrait croiser deux listes, plus laborieux.)

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.