Matrice vers listes

let vers_listes m =
  let n = Array.length m in
  let adj = Array.make n [] in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      if m.(i).(j) then adj.(i) <- j :: adj.(i)
    done
  done;
  adj

Pour chaque ligne i, on ajoute en tête de adj.(i) chaque colonne j marquée. Coût $\Theta (n^2)$ (on lit toute la matrice).