Fiches › Carte › Partie 09 · Coding › coding 06

Graphes — marquer à l'enfilement

Des relations au lieu d'un ordre — voisins, arêtes, cases adjacentes — et des cycles, donc un chemin peut revenir sur ses pas. D'où une seule mécanique, la même pour BFS et pour DFS : un ensemble de vus et une frontière. Et une seule règle qui décide tout le reste — marquer vu à l'enfilement, pas au défilement ; la descendre d'une ligne ne lève aucune erreur et ne change pas la réponse du test qu'on fait à la main. Fil rouge : la grille 3 × 4 1100 / 1100 / 0011, qui a 2 îles, la première étant {0, 1, 4, 5} en indices aplatis ; marquée au défilement, la même course met la case 5 deux fois dans la file. Jamais la solution complète : le squelette, la trace, les phrases.

Ce que cette sheet suppose acquis
  • Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. Ici la boucle est tant que la file n'est pas vide : elle existe, donc l'invariant se récite bien à l'entrée d'un tour, contrairement aux arbres.
  • Invariant = conteneur + tranche + « exactement ». c00, pas 2. Ici il y a deux conteneurs, vu et file, et tout le pattern tient dans la phrase qui les relie — pas 3.
  • Variant = entier ≥ 0 strictement décroissant. c00, pas 3. Ce n'est ni un indice ni la taille de la file (qui monte et descend) : c'est le nombre de sommets non vus.
  • Complexité composée. c00, pas 5. O(V + E) est une somme, pas un produit : deux comptages séparés, l'un sur les sommets, l'autre sur les arêtes — pas 4.
  • Les arbres de c05. Un arbre est le graphe sans cycle et à parent unique : on ne peut pas revenir sur ses pas, donc rien à mémoriser. Toute cette sheet est ce qu'il faut ajouter dès que le cycle redevient possible — c'est-à-dire l'ensemble vu, et rien d'autre.
Hypothèses posées
H1Graphe non pondéré : toutes les arêtes coûtent 1, ou ne coûtent rien. Des poids quelconques changent le problème, pas l'algorithme : c'est Dijkstra, et on le nomme au lieu de le dérouler — hors périmètre de cette sheet, et le pas 7 dit ce que BFS répond quand on oublie de le nommer. H2Les voisins d'un sommet s'énumèrent en O(deg) : liste d'adjacence, ou les 4 voisins d'une case. Une matrice d'adjacence coûte O(V) par sommet, donc O(V2) au total — même parcours, autre facture. H3Une grille est un graphe implicite : on ne construit aucune liste, les voisins se calculent. V = R·C et E = R(C−1) + C(R−1) ; pour 3 × 4, 12 sommets et 17 arêtes. H4Ordre des voisins fixé et annoncé : haut, bas, gauche, droite. Il ne change ni les composantes ni les distances, il change l'ordre de la trace — donc il se dit avant de tracer, sinon la trace au tableau ne tombe pas juste. H5On énonce le squelette et les phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.

La chaîne

Le signal, et le contre-signal tronc

Des relations entre éléments — voisins, arêtes, cases adjacentes, dépendances — et la possibilité d'un cycle. Les questions qui suivent sont toujours les mêmes : connexité, composantes, plus court chemin non pondéré, ordre de dépendances.

relations  +  cycles possibles  ⇒  un ensemble de vus, et une frontière

Deux contre-signaux. Arêtes pondérées : ce n'est plus un parcours mais Dijkstra — on le nomme, on ne l'improvise pas. Aucun cycle et un seul parent : c'est un arbre, et l'ensemble vu devient inutile — c05.

« Le sujet me donne des relations et pas un ordre, et un chemin peut boucler, donc je ne peux pas me contenter d'avancer, donc il me faut retenir ce que j'ai déjà rencontré, donc le pattern est un ensemble de vus doublé d'une frontière. »

Application — le fil rouge : une grille, deux îles

La grille 3 × 4 1100 / 1100 / 0011. Une case à 1 est de la terre, une case à 0 de l'eau, deux cases de terre sont voisines si elles se touchent par un côté. Question : combien d'îles ?

0123 4567 891011

indice aplati = r × 4 + c · ambre = île 1 · vert = île 2

Le graphe est implicite. V = 12, E = 3 × 3 + 4 × 2 = 17 paires de cases voisines — et aucune de ces 17 arêtes n'est écrite nulle part : (r±1, c) et (r, c±1) les fabriquent. C'est le cas le plus fréquent en entretien, et celui où l'on oublie le plus souvent de vérifier les bornes avant d'indexer.

Réponse : 2. Île 1 = {0, 1, 4, 5}, île 2 = {10, 11}. La case 5 est le nœud qui compte : elle a deux voisins déjà découverts — 1 et 4 — donc deux occasions d'entrer dans la file. C'est sur elle que tout le pas 5 se joue.

Cinq questions, un seul parcours. « Combien d'îles », « la plus grande île », « le plus court chemin de A à B », « ces cours peuvent-ils s'ordonner », « ce graphe est-il bipartite » — même boucle, même paire de conteneurs, seul change ce qu'on compte au passage (pas 6).

Le pattern : vus + frontière, et la ligne qui ne se coupe pas tronc

Un ensemble vu et une frontière : une file pour BFS, une pile — explicite ou la récursion — pour DFS. Changer de conteneur change l'ordre de visite et rien d'autre : la charpente est identique.

vu.add(v)  ;  file.append(v)  —  la même ligne, toujours

C'est la règle : on marque au moment où l'on enfile, jamais au moment où l'on défile. Un sommet marqué ne peut plus être enfilé par personne, donc il entre dans la frontière exactement une fois.

« Marquer et enfiler sont deux effets d'un même événement, la découverte, donc je les écris sur la même ligne, donc entre l'entrée d'un sommet dans la file et sa sortie il est déjà vu, donc aucun autre voisin ne peut l'enfiler une seconde fois. »

Application — le squelette, et ce qu'on y branche
pour chaque case (r, c) non vue et à 1 : îles += 1 ; file = deque([(r,c)]) ; vu.add((r,c)) tant que file : (x, y) = file.popleft() pour (nx, ny) dans les 4 voisins : si dans la grille et grille[nx][ny] == 1 et (nx,ny) pas dans vu : vu.add((nx,ny)) ; file.append((nx,ny))

Sept lignes, et trois d'entre elles sont le pattern. La boucle extérieure compte les lancements ; la boucle tant que vide une composante ; la ligne double vu.add … ; file.append … est celle qu'on ne coupe pas.

Le même squelette en DFS : remplacer deque par une liste et popleft() par pop(). Deux caractères. L'ordre de visite change, les composantes sont identiques — mais les distances, elles, ne le sont plus (pas 6).

Ce que la sheet n'aborde pas. Les arêtes pondérées (Dijkstra, A*), les flots, les composantes fortement connexes. Autre sujet, autre sheet : ici, toutes les arêtes valent 1.

Figure 1 — la course correcte : chaque case entre dans la file une fois

Les douze cases de la grille, aplaties : la case d'indice i est la case (i ÷ 4, i mod 4), le grand chiffre est sa valeur, le petit son indice. Ambre = vu, cadre vert = la case qu'on est en train de défiler, et la ligne du bas donne la file réelle — elle n'est pas contiguë dans cette bande, c'est normal, la file suit le graphe et non l'aplatissement. Fais « pas › » et arrête-toi à l'image 4 : on défile la case 1, son voisin du bas est la case 5, elle est déjà vue — parce qu'elle a été marquée quand la case 4 l'a enfilée — donc on ne l'enfile pas. C'est le seul instant de toute la course où la règle sert à quelque chose, et c'est l'instant que la figure 2 supprime. Bilan : 6 enfilements pour 6 cases de terre, 0 doublon, 2 îles.

L'invariant, le variant, la conclusion tronc

L'invariant porte sur les deux conteneurs à la fois, et c'est leur relation qui est l'idée :

vu = les sommets découverts  ·  file ⊆ vu = ceux dont les voisins n'ont pas encore été examinés

La file est donc la frontière de vu : ce qui est vu et pas encore exploité. Variant : le nombre de sommets non vus, entier ≥ 0, qui décroît strictement à chaque enfilement — la file ne reçoit que des sommets non vus, et ils deviennent vus dans le même souffle.

« La file ne contient que des sommets déjà vus, donc chaque enfilement fait décroître d'une unité le nombre de non-vus, donc la boucle s'arrête, donc à file vide plus aucun voisin d'un sommet vu n'est non vu, donc vu est exactement la composante du départ. »

Application — l'invariant récité sur les six images du fil rouge
  • Départ. vu = {0}, file = [0]. Découvert : 1 sommet ; frontière : 1. Non vus : 5 cases de terre.
  • Défile 0. Voisins neufs 4 et 1 → vu = {0, 1, 4}, file = [4, 1]. La case 0 est vue et hors de la frontière : elle est épuisée.
  • Défile 4. Voisin neuf 5 → vu = {0, 1, 4, 5}, file = [1, 5].
  • Défile 1. Son voisin 5 est dans vu → rien n'entre. file = [5]. L'invariant vient de payer.
  • Défile 5. Rien de neuf. file = [].
  • Conclusion. File vide donc vu = {0, 1, 4, 5} est exactement la composante de 0 : un lancement, une composante. Deux lancements donc deux îles.

Le variant, chiffré. 6 cases de terre, 6 enfilements, jamais un de plus. La taille de la file n'est pas le variant : elle vaut 1, 2, 2, 1, 0 — elle remonte, donc elle ne prouve rien.

Vérifié à l'exécution. Le squelette confronté à une union-find indépendante sur des grilles aléatoires : 0 désaccord sur le nombre de composantes.

Le coût : une somme, pas un produit

Deux comptages séparés. Chaque sommet entre dans la file une fois et en sort une fois : O(V). En sortant, on parcourt sa liste de voisins ; la somme des degrés vaut 2E sur un graphe non orienté, donc toutes les listes réunies coûtent O(E).

Σv deg(v) = 2E  ⇒  O(V + E)  ·  espace : O(V) pour vu et pour la file

Sur une grille, E < 2V puisque chaque case a au plus 4 voisins, donc O(V + E) se replie en O(R·C). Sur un graphe dense, au contraire, E vaut jusqu'à V2/2 et c'est E qui domine : la somme n'est pas un ornement.

« Chaque sommet est enfilé une fois et j'examine sa liste de voisins à sa sortie, donc le total des examens est la somme des degrés, donc deux fois le nombre d'arêtes, donc le coût est V plus E — une somme, et sur une grille elle se replie en nombre de cases. »

Application — les chiffres du fil rouge, et l'espace qu'on peut supprimer

Sur la grille 3 × 4. V = 12, E = 17, donc au plus 34 examens de voisin sur l'ensemble de la course — pour 6 enfilements seulement, puisque les 6 cases d'eau ne sont jamais enfilées. Le balayage extérieur, lui, coûte 12 : c'est le terme en V, et il existe même si tout est à 0.

Mesuré, à l'échelle. Grille pleine 300 × 300, soit V = 90 000 : la course correcte fait exactement 90 000 enfilements et la file ne dépasse jamais 300 cases. Le nombre d'enfilements est V au sommet près — c'est l'invariant, vu de l'extérieur.

L'espace, et comment l'annuler. vu coûte O(V). Si l'énoncé autorise à modifier la grille, écrire 0 sur une case visitée remplace l'ensemble : O(1) d'espace auxiliaire. C'est légitime et c'est un bon point en entretien — à condition de le dire, parce que l'appelant récupère sa grille effacée.

Le piège du conteneur. vu en set de tuples : test en O(1). En liste, in est O(V), donc le parcours passe de O(V + E) à O(V·E) — une seule structure de données mal choisie, et la complexité annoncée devient fausse.

Le bug qui ne plante pas : marquer au défilement casse

On descend vu.add() d'une ligne, sous le popleft(), et on ajoute un garde-fou si déjà vu : continuer. Le code reste lisible, la réponse reste juste sur les petits cas. Mais entre l'enfilement d'un sommet et son défilement, il n'est marqué nulle part.

frontière ⊆ sommets (enfilement)  →  frontière ⊆ arêtes (défilement)

Donc tout voisin encore à traiter peut l'enfiler à son tour. Un sommet entre alors une fois par arête entrante : la file compte jusqu'à O(E) éléments au lieu de O(V).

« Un sommet enfilé n'est pas marqué avant de sortir, donc chacun de ses voisins encore dans la file peut l'enfiler à nouveau, donc il entre une fois par arête entrante au lieu d'une fois en tout, donc la file grossit comme E et non comme V — sans qu'aucune exception ne soit levée. »

Application — la case 5, deux fois ; et ce que ça coûte vraiment

Sur le fil rouge. La case 4 enfile 5. La case 1 défile ensuite, regarde son voisin du bas : 5 n'est pas dans vu — il n'est que dans la file — donc elle l'enfile une seconde fois. file = [5, 5]. Le second 5 sortira, se trouvera déjà vu et sera jeté. 5 enfilements pour 4 cases, et la réponse reste 2 îles.

Le surcoût, mesuré. Sur une grille il est modeste, parce que E ≈ 2V : grille pleine 300 × 300, 179 400 enfilements au lieu de 90 000 (×2), file maximale 599 au lieu de 300. Sur un graphe dense il explose : sur K500 (500 sommets, 124 750 arêtes), 124 751 enfilements au lieu de 500 — ×250 — et la file monte à 124 252 éléments. C'est le sens exact de « quadratique » : le coût suit E, qui vaut V2/2.

Pourquoi c'est indétectable à la main. Il faut un sommet ayant deux voisins simultanément dans la frontière. Sur un chemin — une grille en serpentin, une liste — cela n'arrive jamais : la version fautive produit alors trace pour trace la même course que la bonne. Le fil rouge a été choisi carré, pas en L, précisément pour que le doublon existe.

Et les distances, elles, deviennent fausses. Version qui écrit dist[u] = k au défilement sans garde-fou : 39,4 % de 20 000 graphes aléatoires donnent des distances fausses. Le plus petit témoin est un triangle — arêtes 0–1, 0–2, 1–2 : les vraies distances depuis 0 sont {1 : 1, 2 : 1}, la version fautive renvoie {1 : 1, 2 : 2}, parce que le second exemplaire du sommet 2, enfilé par 1, écrase le premier.

Figure 2 — la même course, vu.add() descendu d'une ligne

Même grille, même ordre de voisins, une seule ligne déplacée. Compare image par image avec la figure 1 : les trois premières sont identiques. Arrête-toi à l'image 4. En figure 1 la case 5 était ambre — vue — et la case 1 passait son chemin ; ici elle est blanche, parce que personne ne l'a marquée : elle n'est que dans la file. Donc la case 1 l'enfile, et la ligne inv affiche file = [5, 5]. Aux images 5 et 6 les deux exemplaires sortent l'un après l'autre, le second est jeté, et la réponse finale est la même — 2 îles. C'est tout le sujet : rien ne plante, rien ne change, sauf le nombre d'enfilements (5 au lieu de 4) et, dès qu'on demande des distances, la réponse elle-même.

Les variantes : même boucle, autre chose à compter

Une fois la charpente posée, chaque question classique tient en une ligne. Distances non pondérées : BFS, dist[v] = dist[u] + 1 posé à l'enfilement ; le premier défilement d'une cible est optimal. Composantes : compter les lancements de la boucle extérieure. Bipartition : BFS en alternant deux couleurs, un conflit sur une arête et c'est non.

cycle orienté : arête vers un gris  ·  ordre topologique : empiler à la sortie, puis inverser

Les deux dernières sont du DFS et se trompent au même endroit : elles se lisent à la sortie de l'appel, pas à l'entrée. Blanc / gris / noir — gris = en cours, noir = fini ; une arête vers un noir n'est pas un cycle.

« Le blanc n'est pas encore vu, le gris est en cours dans la pile d'appels courante et le noir est fini, donc une arête vers un gris boucle sur un ancêtre, donc c'est un cycle, donc une arête vers un noir ne prouve rien — elle rejoint seulement un sous-graphe déjà terminé. »

Application — les trois variantes qui se ratent, chiffrées

L'ordre topologique. Empiler à la sortie puis inverser : 0 ordre faux sur 50 000 DAG aléatoires. Empiler à l'entrée (un simple pré-ordre) : 80,5 % d'ordres faux. Le plus petit témoin a trois sommets — A→B, A→C, C→B : le pré-ordre sort A, B, C et place B avant C, alors que C→B l'exige après.

Le cycle à trois couleurs. Confronté à Kahn (degrés entrants, file des 0) sur 50 000 graphes orientés aléatoires : 0 désaccord. Le contre-exemple à connaître pour le faux positif : le DAG A→B, A→C, B→D, C→D. En visitant C on trouve D déjà noir ; le prendre pour un cycle donne « cycle » sur un graphe qui n'en a aucun. Un ensemble vu à deux états ne suffit donc pas ici — il en faut trois.

Kahn, la version sans récursion. Degrés entrants, file des sommets de degré 0, et on décrémente. Même O(V + E), et elle détecte le cycle gratuitement : si moins de V sommets sortent de la file, il reste un cycle. À préférer dès que le graphe est gros, puisqu'il n'y a plus de pile d'appels.

DFS ou BFS ? Pour les composantes et le cycle, indifférent. Pour les distances, BFS obligatoire : un DFS atteint les sommets dans un ordre quelconque et le premier chemin trouvé n'a aucune raison d'être le plus court.

Figure 3 — ordre topologique : empiler à la sortie, ou à l'entrée

Le DAG A→B, A→C, C→B, C→E, B→D, E→D : cinq tâches, six dépendances, une flèche se lit « doit passer avant ». Le badge sur chaque sommet est son rang dans l'ordre produit. Clique post-ordre inversé : l'ordre est A, C, E, B, D et les six flèches pointent toutes vers un rang plus grand — 0 violation. Clique pré-ordre : le DFS écrit chaque sommet en y entrant, donc il sort A, B, D, C, E ; deux flèches passent au rouge pointillé, C→B et E→D, parce que le parcours a plongé dans B avant d'avoir même découvert C. Ce que la figure fait voir : on ne peut pas placer un sommet tant qu'on n'a pas fini tous ses descendants — et « avoir fini » est exactement ce que le post-ordre attend et ce que le pré-ordre ne sait pas.

Où ça casse casse

Le cas fatal est silencieux : lancer un BFS sur un graphe dont les arêtes ont des poids. La fonction ne lève rien, ne ralentit pas, et rend un chemin — celui qui a le moins d'arêtes. Ce n'est pas le moins cher, et rien dans la sortie ne le signale.

Le mécanisme : le BFS ne compare jamais deux coûts, il compte des tours de boucle. Il est optimal exactement quand toutes les arêtes valent 1, parce qu'alors « le moins d'arêtes » et « le moins cher » sont la même phrase.

« Le BFS visite par nombre d'arêtes et ne regarde aucun poids, donc il rend le chemin le plus court en arêtes, donc dès qu'un poids diffère de 1 ce chemin n'est plus le moins cher, donc il renvoie un nombre parfaitement faux sans lever la moindre erreur. »

Le contre-exemple minimal, à sortir de mémoire

Trois sommets suffisent. A→B de poids 5, A→C de poids 1, C→B de poids 1. Le BFS atteint B en 1 arête et annonce ce chemin ; son coût réel est 5. Le chemin A→C→B coûte 2. La bonne réponse est 2, le BFS dit 5 — ou, pire, dit « 1 » si l'on compte les arêtes en croyant compter le coût.

La phrase qui tue. « Le BFS compte des arêtes, pas des poids — donc il est optimal si et seulement si toutes les arêtes valent 1. Sinon, Dijkstra. » Elle se dit sans dessiner, et elle nomme ce qu'on ne va pas dérouler.

Le second silence, même famille. Le marquage au défilement sur un BFS de distances : 39,4 % de graphes aléatoires donnent des distances fausses, et le plus petit témoin est un triangle — voir le pas 5. Là encore : un nombre, poliment, et il est faux.

Le troisième. Prendre une arête vers un sommet noir pour un cycle : sur le DAG A→B, A→C, B→D, C→D, la détection à deux états annonce un cycle qui n'existe pas. Un faux positif, pas une exception.

Pièges Python — quatre lignes qui ont l'air justes
  • list.pop(0) au lieu de deque.popleft(). Un pop(0) décale toute la liste : O(n) par défilement, donc O(n2) pour vider la file. Mesuré sur 200 000 éléments : 3,5 s contre 0,011 s — un facteur 334. Et rien ne plante : le code passe les petits tests et meurt sur le grand.
  • Indexer avant de tester les bornes. grille[nx][ny] == 1 and 0 <= nx < R lit hors grille — et en Python grille[-1] ne lève rien : il rend la dernière ligne. Une grille devient un tore, les composantes fusionnent, aucune erreur. Les bornes d'abord, toujours.
  • vu en liste. (nx,ny) not in vu est O(V) sur une liste et O(1) sur un set de tuples : le parcours passe de O(V + E) à O(V·E). Même réponse, autre complexité — donc autre verdict en entretien.
  • RecursionError vers 1 000 niveaux. Un DFS récursif sur une grille 1 000 × 1 000 descend jusqu'à un million d'appels. Mesuré avec sys.getrecursionlimit() = 1000 : la chaîne passe à 997 appels et lève à 998. Réponse : pile explicite ou BFS ; sys.setrecursionlimit marche aussi, à condition de le dire — on déplace la limite, on ne la retire pas, et le segfault remplace l'exception.

Résumé

À retenir
  1. Signal : des relations et des cycles possibles ⇒ un ensemble de vus et une frontière. File = BFS, pile = DFS, le reste est identique.
  2. La règle : vu.add(v) et file.append(v) sur la même ligne. Marquer à l'enfilement, jamais au défilement.
  3. Invariant : vu = découverts, file = frontière de vu. Variant : le nombre de non-vus, jamais la taille de la file.
  4. Coût : O(V + E) — une somme. Espace O(V), ou O(1) en marquant in-place si on le dit.
  5. BFS pour les distances par niveaux ; DFS pour composantes, cycle (trois couleurs, arête vers un gris) et topo (empiler à la sortie, inverser).
  6. Pondéré ⇒ Dijkstra, et on le nomme : le BFS rend le chemin le plus court en arêtes, poliment faux. A→B poids 5 contre A→C→B poids 2.
  7. Récursion : lève vers 1 000 niveaux (mesuré : 998). Pile explicite, ou BFS.
« Un parcours de graphe, c'est un ensemble de vus et une frontière ; je marque à l'enfilement pour que chaque sommet entre une fois, ce qui donne V plus E. BFS me donne les distances par niveaux, DFS suffit pour les composantes, la détection de cycle à trois couleurs et l'ordre topologique en empilant à la sortie. Sur une grille, la récursion casse vers mille niveaux : pile explicite. Et si les arêtes sont pondérées, ce n'est plus un parcours, c'est Dijkstra. »

Chaîne verbalisée — une prise, à voix haute

5 maillons · clique pour révéler après avoir dit
  1. Quel est l'invariant d'un BFS ?
    vu = les sommets découverts ; la file = la frontière de vu, c'est-à-dire ceux dont les voisins n'ont pas encore été examinés. Conséquence : chaque sommet entre dans la file exactement une fois. Le variant est le nombre de non-vus, pas la taille de la file — elle remonte.
  2. Pourquoi marquer à l'enfilement et pas au défilement ?
    Parce qu'entre l'enfilement et le défilement, un sommet non marqué peut être enfilé par chacun de ses autres voisins. La file grossit alors comme E au lieu de V — ×250 sur un graphe complet à 500 sommets — et en BFS de distances, la réponse elle-même devient fausse : 39 % des graphes aléatoires. Rien ne plante.
  3. Complexité, et pourquoi cette forme ?
    O(V + E), une somme : O(V) parce que chaque sommet est enfilé une fois, O(E) parce que la somme des degrés vaut 2E. Espace O(V) pour vu et la file, ou O(1) si on a le droit de marquer in-place dans la grille — à annoncer, l'appelant récupère sa grille effacée.
  4. Ordre topologique par DFS, et où il se rate ?
    Empiler à la sortie de l'appel — le post-ordre — puis inverser. Empiler à l'entrée donne un ordre faux 4 fois sur 5 ; témoin à trois sommets : A→B, A→C, C→B, dont le pré-ordre sort A, B, C. Sans récursion : Kahn, degrés entrants et file des zéros, qui détecte le cycle en prime.
  5. Cycle dans un graphe orienté ?
    Trois couleurs : blanc non vu, gris en cours dans la pile courante, noir terminé. Une arête vers un gris est un cycle ; une arête vers un noir n'est rien du tout — sur le DAG A→B, A→C, B→D, C→D on retombe sur un D noir sans qu'aucun cycle existe. Deux états ne suffisent pas.