Parcours en profondeur

let parcours_profondeur adj depart =
  let n = Array.length adj in
  let vu = Array.make n false in
  let ordre = ref [] in
  let rec visite s =
    if not vu.(s) then begin
      vu.(s) <- true;
      ordre := s :: !ordre;
      List.iter visite adj.(s)
    end
  in
  visite depart;
  !ordre

La récursion s'enfonce dans le premier voisin non vu, puis remonte. ordre accumule les sommets dans l'ordre inverse de découverte (chaque nouveau est mis en tête).