Probleme – Le même parcours, deux structures

....#          la case (0,0) est en haut a gauche
.##.#          # est un mur
.#...
...#.

1. Le parcours générique.

/* Explore la composante de la case de depart. La reserve n'est employee
   que par : deposer, retirer, est_vide. AUCUNE autre hypothese.
   dist[c] est la distance de c au depart DANS L'ARBRE DE PARCOURS. */
void parcourir(reserve* r) {
    marquer(depart); dist[depart] = 0; deposer(r, depart);
    while (!est_vide(r)) {
        case p = retirer(r);
        visiter(p);
        for (chaque voisin v de p) {
            if (praticable(v) && !marque(v)) {
                marquer(v);                 /* on marque en DEPOSANT, */
                dist[v] = dist[p] + 1;      /* pas en retirant */
                deposer(r, v);
            }
        }
    }
}

Un détail qui n'en est pas un : on marque au moment de déposer, non au moment de retirer. Sans cela, une case atteignable par deux chemins serait déposée deux fois, et la réserve pourrait contenir $\Theta (n)$ doublons. Le marquage précoce garantit que chaque case est déposée exactement une fois, donc que le parcours est en $\Theta (\text{cases}+\text{voisinages})$.

2. Les deux exécutions. Mesuré, avec les voisins essayés dans l'ordre haut, bas, gauche, droite :

PILE (profondeur)
 ordre : (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (3,4)
         (2,2) (3,2) (3,1) (3,0) (2,0) (1,0)
 dist :   0   1   2   3   #
          1   #   #   4   #
         10   #   6   5   6
          9   8   7   #   7

FILE (largeur)
 ordre : (0,0) (1,0) (0,1) (2,0) (0,2) (3,0) (0,3) (3,1)
         (1,3) (3,2) (2,3) (2,2) (2,4) (3,4)
 dist :   0   1   2   3   #
          1   #   #   4   #
          2   #   6   5   6
          3   4   5   #   7

Le code est le même, les résultats ne le sont pas. La pile visite $(0,1)$, $(0,2)$, $(0,3)$ d'affilée : elle suit un couloir jusqu'au bout. La file visite $(1,0)$ et $(0,1)$ avant $(2,0)$ : elle progresse par cercles concentriques.

3. C'est la file qui donne les plus courts chemins. On le lit sur la case $(2,0)$ : la file lui attribue $2$, qui est bien sa distance ; la pile lui attribue $10$, parce qu'elle y est arrivée après avoir fait le tour complet de la grille.

Pourquoi la file y arrive. Invariant : à tout instant, la file contient des cases dont les distances valent $d$ puis $d+1$, dans cet ordre, pour un certain $d$. Il est vrai au départ. Quand on retire une case de distance $d$, on y ajoute des voisins de distance $d+1$, à la fin — donc après toutes les cases de distance $d$ encore présentes, et avant aucune case de distance $d$. L'invariant est préservé, les cases sortent donc par distance croissante, et la première fois qu'une case est atteinte, c'est par un chemin de longueur minimale.

Pourquoi la pile n'y arrive pas. Elle retire la case déposée en dernier, c'est-à-dire la plus récemment découverte, sans aucun rapport avec sa distance. La valeur dist qu'elle calcule est la profondeur dans l'arbre de parcours, ce qui est une grandeur parfaitement définie mais qui n'est pas la distance dans la grille.

Le point à emporter. Un même algorithme, une même preuve de terminaison, une même complexité — et deux propriétés différentes, toutes deux utiles. La pile donne la profondeur, qui sert à détecter les cycles et à ordonner topologiquement ; la file donne les distances. Le chapitre chap:parcours construira les deux sur des graphes quelconques et démontrera ces propriétés dans le cas général ; ce problème n'a fait que les rendre visibles sur seize cases.