Marquer au retrait : chiffrer ce que cela coûte

Mesures (nombre total d'entrées dans la réserve, parcours en largeur depuis $0$) :

La colonne de droite vaut systématiquement $m+1$.

La borne, et sa démonstration. Chaque insertion de $v$ est provoquée par le traitement d'un voisin $u$, donc par une arête $\{u,v\}$. Une même arête ne peut servir deux fois : une fois $u$ retiré et marqué, il n'est plus jamais traité. Le nombre total d'insertions est donc au plus $m+1$ (la source comprise). C'est atteint sur les graphes ci-dessus, où tout sommet a des voisins encore non marqués au moment où on l'examine.

Ce que cela coûte réellement. La réserve contient $\Theta (m)$ éléments au lieu de $\Theta (n)$ : c'est la mémoire qui explose, pas le temps. Sur $K_{50}$, la file monte à $1177$ éléments au lieu de $49$. Le temps reste $\Theta (n+m)$, puisque chaque insertion est en $O(1)$ et qu'il y en a $O(m)$.

Une nuance sur l'affirmation du chapitre. Le chapitre écrit « la complexité pourrait exploser — jusqu'à $O(m^2)$ ». La mesure ne le confirme pas : même en supprimant tout test avant l'empilement, on plafonne à $2m+1$ insertions ($2451$ mesurées sur $K_{50}$, pour $m=1225$). Le surcoût est un facteur $m/n$, pas un carré. Cela n'affaiblit pas la règle : marquer à l'ajout reste la seule écriture correcte, et la raison en est la mémoire. Mais elle mérite d'être dite juste.