DFS itératif avec pile explicite

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

La pile remplace la pile d'appels de la version récursive. Subtilité : un sommet peut être empilé plusieurs fois (par différents voisins) ; on le marque donc au moment où on le dépile, et l'on ignore les doublons déjà vus. Remplacer la Stack par une Queue transformerait ce DFS en BFS — preuve que c'est la structure (pile ou file) qui distingue les deux parcours.