Parcours en largeur

let parcours_largeur adj depart =
  let n = Array.length adj in
  let vu = Array.make n false in
  let f = Queue.create () in
  let ordre = ref [] in
  vu.(depart) <- true;
  Queue.push depart f;
  while not (Queue.is_empty f) do
    let s = Queue.pop f in
    ordre := s :: !ordre;
    List.iter (fun v ->
      if not vu.(v) then begin vu.(v) <- true; Queue.push v f end
    ) adj.(s)
  done;
  !ordre

La file impose l'ordre « premier découvert, premier traité » : les sommets sortent de la file par distance croissante au départ ; !ordre les rend en ordre inverse (chaque sommet est mis en tête), List.rev !ordre donne l'ordre de visite.