Le parcours en profondeur itératif n'est pas le récursif

let profondeur_pile g s =
  let vu = Array.make (Array.length g) false and pile = ref [s] in
  vu.(s) <- true;
  while !pile <> [] do
    let u = List.hd !pile in pile := List.tl !pile;
    traiter u;
    List.iter (fun v -> if not vu.(v) then begin vu.(v) <- true; pile := v :: !pile end) g.(u)
  done

Non, et l'écart est spectaculaire. Sur le graphe à huit sommets du premier exercice de ce chapitre :

recursif                        : 0 1 3 6 4 5 2 7
iteratif avec la pile ci-dessus : 0 2 5 6 7 4 3 1

Les deux visitent bien tous les sommets — ce sont deux parcours en profondeur valides — mais dans des ordres presque opposés.

Deux causes, et il faut les corriger toutes les deux.

• La pile inverse l'ordre des voisins. On empile $1$ puis $2$ ; on dépile $2$ d'abord. La version récursive, elle, appelle $1$ d'abord. Empiler les voisins à l'envers corrige ce point.
• Le moment du marquage diffère. La récursion marque $u$ quand elle le visite ; la pile ci-dessus le marque quand elle l'empile, donc bien avant. Un sommet atteignable par deux chemins sera donc marqué depuis le mauvais.

Mesure de la correction partielle : en empilant seulement les voisins à l'envers, on obtient 0 1 3 6 5 7 4 2 — toujours différent du récursif. Il faut les deux corrections :

(* Parcours en profondeur iteratif REPRODUISANT exactement l'ordre recursif.
   Precondition : 0 <= s < Array.length g.
   Complexite : Theta(n + m) en temps, O(m) en memoire (la pile). *)
let profondeur_fidele g s =
  let vu = Array.make (Array.length g) false and pile = ref [s] in
  while !pile <> [] do
    let u = List.hd !pile in pile := List.tl !pile;
    if not vu.(u) then begin           (* on MARQUE AU RETRAIT, comme la recursion *)
      vu.(u) <- true;
      traiter u;
      List.iter (fun v -> if not vu.(v) then pile := v :: !pile)
        (List.rev g.(u))               (* et on empile les voisins A L'ENVERS *)
    end
  done

Mesure : 0 1 3 6 4 5 2 7, identique au récursif — vérifié aussi sur un second graphe orienté, pour ne pas conclure d'un seul cas.

Le prix à payer, et il faut le savoir. Cette version marque au retrait : elle retombe donc exactement dans le défaut de l'exercice précédent, et sa pile peut contenir $\Theta (m)$ éléments. Les trois versions se rangent ainsi :

La troisième version est la simulation exacte de la récursion : on empile non pas les voisins, mais le sommet accompagné de l'indice où l'on en est dans sa liste d'adjacence — c'est-à-dire le bloc d'activation du chapitre chap:memoire, reconstitué à la main. Elle a les deux qualités, et un code deux fois plus long. Quand l'ordre n'importe pas — accessibilité, composantes connexes —, on prend la première ; quand il importe — tri topologique, numérotation préfixe et suffixe —, on écrit la récursion, et l'on ne descend à la pile explicite que si la profondeur menace de la faire déborder.