Tri topologique : combien y en a-t-il, et que se passe-t-il s'il y a un cycle ?

Le tri produit par l'algorithme (visite depuis $0$, listes d'adjacence croissantes) : 0 2 5 1 3 4.

Il peut surprendre : $1$ arrive après $2$ et $5$, alors que l'arc $0\to 1$ le rendait disponible dès le départ. C'est le postfixe : $1$ est empilé quand sa visite se termine, et sa visite a commencé après celle de $2$ dans la remontée.

Tous les tris valides, obtenus par énumération exhaustive : il y en a exactement cinq.

0 1 2 3 5 4      0 2 1 3 5 4
0 1 2 5 3 4      0 2 1 5 3 4
                 0 2 5 1 3 4     <-- celui que rend l'algorithme

Le tri topologique n'est jamais unique sauf si le graphe contient un chemin passant par tous les sommets. Ici $1$ et $2$ sont incomparables, $3$ et $5$ aussi : chaque incomparabilité multiplie les possibilités.

Avec un cycle, l'algorithme ne signale rien. Sur $0\to 1\to 2\to 3\to 1$, il rend 0 1 2 3 — un ordre où l'arc $3\to 1$ va de l'arrière vers l'avant. Le résultat est faux, et silencieusement. La démonstration du chapitre l'annonçait : elle utilise l'acyclicité dans son second cas, celui où $v$ est déjà vu.

Comment détecter le cycle sans coût supplémentaire : on colorie les sommets en trois états au lieu de deux.

(* Tri topologique de g, ou None si g contient un circuit.
   Complexite : Theta(n + m). *)
exception Circuit
let tri_topologique_sur g =
  let n = Array.length g in
  let couleur = Array.make n 0 in     (* 0 blanc, 1 GRIS (en cours), 2 noir *)
  let ordre = ref [] in
  let rec visiter u =
    couleur.(u) <- 1;
    List.iter (fun v ->
      if couleur.(v) = 1 then raise Circuit   (* arc ARRIERE : un circuit *)
      else if couleur.(v) = 0 then visiter v) g.(u);
    couleur.(u) <- 2;
    ordre := u :: !ordre
  in
  try for s = 0 to n - 1 do if couleur.(s) = 0 then visiter s done; Some !ordre
  with Circuit -> None

C'est le gris qui porte toute l'information : un arc vers un sommet gris est un arc vers un ancêtre encore en cours de visite, donc un arc arrière, donc un circuit. Un arc vers un sommet noir est un arc avant ou transverse, et ne prouve rien. Deux couleurs ne permettent pas de faire la différence — c'est exactement ce qui manque à la version du chapitre.