Parcours de graphes

Terminaison : chaque sommet entre au plus une fois dans la pile (on n'empile que des non-marqués, et l'on marque en empilant) ; chaque tour de boucle dépile un élément. Le nombre total de dépilements est donc borné par $n$ : variant $=$ (nombre de sommets jamais empilés) $+$ (taille de la pile), qui décroît strictement à chaque tour. Correction — l'invariant à double face : (i) tout sommet marqué est accessible depuis la source (on ne marque que des voisins de sommets accessibles : récurrence immédiate) ; (ii) à la fin, tout sommet accessible est marqué — sinon, sur un chemin de la source vers un sommet non marqué, il existerait une première arête $(u,v)$ avec $u$ marqué et $v$ non marqué ; or $u$ marqué a été dépilé (la pile finit vide) et son voisin $v$ aurait alors été marqué : contradiction. Le parcours visite exactement l'ensemble accessible. (Cette preuve, une fois acquise, vaut pour tous les parcours : elle n'utilise nulle part l'ordre de la pile.)

Par récurrence sur $d$ : tous les sommets à distance $d$ entrent dans la file avant tout sommet à distance $d+1$, et avec la bonne étiquette. Pour $d=0$ : la source. Si la propriété vaut jusqu'à $d$ : un sommet $v$ à distance $d+1$ a, par définition, un voisin $u$ à distance $d$ ; quand $u$ — correctement étiqueté, et défilé avant tout sommet de distance $>d$ — examine ses voisins, il marque $v$ avec $d+1$ s'il ne l'est pas déjà ; et $v$ ne peut pas avoir été marqué plus tôt avec une étiquette plus grande (les marquages se font par étiquettes croissantes, ordre FIFO). (C'est l'ordre premier-entré-premier-sorti qui porte toute la preuve : avec une pile, les étiquettes seraient fausses — le DFS ne calcule pas les distances, et c'est le contre-exemple à connaître.)

(a) Pile (LIFO) : retirés $2$ (dernier entré), puis $4$, puis $3$ ; état final $[1]$. (b) File (FIFO) : retirés $1$ (premier entré), puis $2$, puis $3$ ; état final $[4]$. (Le même scénario, deux histoires : la pile traite l'urgence du moment, la file honore l'ancienneté — exactement la différence DFS/BFS qui s'ensuit.)

Largeur : file $[a]$ ; défiler $a$, marquer-enfiler $b,c\to [b,c]$ ; défiler $b$, voisin $a$ vu, marquer $d\to [c,d]$ ; défiler $c$, marquer $e\to [d,e]$ ; défiler $d$, marquer $f\to [e,f]$ ; défiler $e$ ($f$ déjà vu) $\to [f]$ ; défiler $f$. Ordre : $a,b,c,d,e,f$. ✓

Profondeur récursive : depuis $a$, premier voisin $b$ ; depuis $b$, voisin $d$ ; depuis $d$, voisin $f$ ; depuis $f$, voisin $e$ ; depuis $e$, voisin $c$ ; tout remonte. Ordre : $a,b,d,f,e,c$ — différent de l'itératif ($a,c,e,f,d,b$), qui dépile le dernier voisin empilé et explore donc les listes à rebours. (Deux DFS légitimes : « un » parcours en profondeur n'est pas unique, seul l'ensemble visité l'est — toute question d'ordre doit préciser la variante, et les deux satisfont la même preuve.)

def existe_chemin(G: dict, u, v) -> bool:
    if u == v:
        return True
    vus = {u}
    pile = [u]
    while pile:
        s = pile.pop()
        for w in G[s]:
            if w == v:
                return True           # arrêt anticipé
            if w not in vus:
                vus.add(w)
                pile.append(w)
    return False

Pire cas $O(n+m)$ : si $v$ est inaccessible (ou découvert en dernier), tout l'accessible est exploré avant de conclure — l'arrêt anticipé améliore les cas favorables, jamais la garantie, exactement comme le drapeau du tri à bulles (chapitre 3). (Le cas $u=v$ traité d'emblée est le cas limite du partitionnement, chapitre 10 — et la convention « chemin de longueur 0 » que la spécification doit trancher.)

import time
n = 100_000
etoile = {0: list(range(1, n + 1))}        # le hub...
for i in range(1, n + 1):
    etoile[i] = [0]                        # ... et ses abonnés

debut = time.perf_counter()
parcours_largeur(etoile, 0)                # version deque
t_deque = time.perf_counter() - debut      #   0,01 s

# même code avec : file = [source] ... s = file.pop(0)
t_liste = ...                              #   0,9 s : facteur 80 !

(a) L'étoile : dès le premier tour, les $10^5$ voisins du hub entrent dans la file ; chaque pop(0) décale alors $\sim 10^5$ éléments — coût total $O(n^2)$, mesuré : facteur $\sim 80$, et il croît linéairement avec $n$. (b) La grille, verdict surprenant : les deux versions font quasiment jeu égal ! La raison tient dans la longueur de la file : lors d'un parcours en largeur, la file contient la frontière de l'exploration — sur une grille, un « cercle » d'au plus $\sim 2\sqrt{n}$ cases (quelques centaines), et décaler quelques centaines de cases est trop rapide pour se voir. Le coût du pop(0) est $O(\text{longueur courante de la file})$ : tout dépend du graphe — file courte, piège invisible ; file longue (hubs, graphes denses — et les réseaux réels ont des hubs), parcours quadratique. (La leçon mûre : une mauvaise complexité peut rester indolore sur mille entrées et exploser sur la mille-et-unième — comme on ne choisit pas le graphe qu'on recevra, on choisit deque, dont la garantie ne dépend de rien.)

def resoudre_labyrinthe(plan: list, E: tuple, S: tuple):
    """plan : liste de chaînes. Renvoie (distance, chemin) ou (None, None)."""
    p, q = len(plan), len(plan[0])
    dist, pere = {E: 0}, {}
    file = deque([E])
    while file:
        (i, j) = file.popleft()
        if (i, j) == S:
            break                                  # la première atteinte est la bonne
        for (ni, nj) in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= ni < p and 0 <= nj < q and plan[ni][nj] == "." \
               and (ni, nj) not in dist:
                dist[(ni, nj)] = dist[(i, j)] + 1
                pere[(ni, nj)] = (i, j)
                file.append((ni, nj))
    if S not in dist:
        return (None, None)
    return (dist[S], chemin(pere, E, S))

Le graphe n'est même pas construit : les voisins se calculent à la volée depuis le plan — un graphe implicite, économie majeure quand la grille est grande. La largeur garantit que la première fois que $S$ sort de la file, sa distance est minimale (théorème du cours) : l'arrêt est licite. (Tout y est : la grille du chapitre 12, le théorème des distances, les pères, l'arrêt anticipé — le labyrinthe est l'examen blanc du parcours en largeur, et la version en profondeur trouverait un chemin, mais pas le plus court : tester les deux sur un labyrinthe à deux routes inégales est l'expérience à faire.)

def est_un_arbre(G: dict) -> bool:                 # (a)
    return est_connexe(G) and not a_un_cycle(G)

def est_un_arbre_compte(G: dict) -> bool:          # (b)
    nb_aretes = sum(len(G[s]) for s in G) // 2     # chaque arête comptée 2 fois
    return est_connexe(G) and nb_aretes == len(G) - 1

chaine = {0: [1], 1: [0, 2], 2: [1]}
triangle = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
foret = {0: [1], 1: [0], 2: []}
for g in (chaine, triangle, foret):
    assert est_un_arbre(g) == est_un_arbre_compte(g)
assert est_un_arbre(chaine) and not est_un_arbre(triangle) and not est_un_arbre(foret)

Les deux fonctions implémentent les deux caractérisations équivalentes de la proposition du cours ; la version (b) remplace une détection de cycle par un comptage — plus simple, à condition d'avoir déjà la connexité (la forêt à deux composantes a bien $n-1=2$ arêtes… non : $1$ arête pour $3$ sommets — et c'est la connexité qui la rejette). (Tester l'équivalence de deux implémentations indépendantes : le test croisé du chapitre 1, ici au service d'un théorème — chaque assertion qui passe est une instance vérifiée de la proposition.)

def est_biparti(G: dict) -> bool:
    couleur = {}
    for depart in G:                          # toutes les composantes
        if depart in couleur:
            continue
        couleur[depart] = 0
        file = deque([depart])
        while file:
            s = file.popleft()
            for v in G[s]:
                if v not in couleur:
                    couleur[v] = 1 - couleur[s]
                    file.append(v)
                elif couleur[v] == couleur[s]:
                    return False              # arête dans un camp : impossible
    return True

cycle4 = {i: [(i - 1) % 4, (i + 1) % 4] for i in range(4)}
cycle5 = {i: [(i - 1) % 5, (i + 1) % 5] for i in range(5)}
assert est_biparti(cycle4) and not est_biparti(cycle5)

Justification : si le graphe est biparti, les deux camps alternent le long de tout chemin — la couleur doit être la parité de la distance, et le coloriage du parcours est le seul candidat ; s'il échoue (deux voisins de même couleur), aucun partage n'existe. Le cycle pair alterne sans heurt ; le cycle impair se mord la queue — son tour complet rend une couleur contradictoire. (Au passage, un théorème célèbre se touche du doigt : un graphe est biparti si et seulement s'il n'a aucun cycle impair — le parcours en largeur en est la preuve algorithmique, et le contre-exemple minimal est le triangle.)

Modèle : sommets $=$ mots du lexique ; arête si les mots diffèrent d'exactement une lettre (même longueur). Construction du graphe en comparant toutes les paires ($O(L^2\cdot \ell )$ pour $L$ mots de $\ell$ lettres) :

def different_d_une_lettre(u: str, v: str) -> bool:
    return len(u) == len(v) and sum(1 for a, b in zip(u, v) if a != b) == 1

lexique = ["rame", "race", "rage", "cage", "came", "cape", "rape"]
G = {m: [v for v in lexique if different_d_une_lettre(m, v)] for m in lexique}

Résolution : parcours en largeur depuis rame avec pères, puis reconstruction. Les distances calculées : race et rage et came et rape à $1$ ; cage à $2$ (via rage) — chemin : $\text{rame}\to \text{rage}\to \text{cage}$, de longueur $2$, et le théorème garantit qu'aucune échelle plus courte n'existe. (Le jeu de Lewis Carroll, devenu cas d'école : un problème de mots sans aucun « graphe » apparent, entièrement résolu par modélisation $+$ BFS — la chaîne complète des compétences du programme sur sept mots. Avec un vrai lexique de $10^5$ mots, la construction par paires devient le goulot : l'astuce des classes r_me — remplacer chaque lettre par un joker et grouper par dictionnaire, chapitre 2 ! — la ramène au linéaire.)

Établissons d'abord les deux lemmes admis-utilisables, qui font tout le travail. Lemme A (connexe $\Rightarrow \ge n-1$ arêtes) : un parcours depuis un sommet quelconque atteint les $n-1$ autres, et chacun est découvert via une arête nouvelle (celle de son père) — $n-1$ arêtes distinctes au moins. Lemme B (sans cycle $\Rightarrow \le n-1$ arêtes) : par récurrence sur $n$ ; un graphe sans cycle non vide a un sommet de degré $\le 1$ (suivre un chemin sans répéter de sommet — possible sans cycle — jusqu'à un cul-de-sac) ; le retirer ôte au plus une arête et préserve l'acyclicité : au plus $1+((n-1)-1)=n-1$ arêtes.

(i) $\Rightarrow$ (ii) : connexe donne $\ge n-1$ (A), sans cycle donne $\le n-1$ (B) : exactement $n-1$. (ii) $\Rightarrow$ (iii) : si un cycle existait, retirer une arête du cycle préserverait la connexité (tout chemin par cette arête se détourne par le reste du cycle) — un graphe connexe à $n-2$ arêtes contredirait le lemme A. (iii) $\Rightarrow$ (i) : notons $k$ le nombre de composantes connexes ; chaque composante, connexe et sans cycle, possède (par (i)$\Rightarrow$(ii) appliqué à elle-même) $n_j-1$ arêtes ; le total $n-k$ doit valoir $n-1$ : $k=1$, connexe. (Le théorème dit que les arbres vivent sur un fil : une arête de plus crée un cycle, une de moins déconnecte — c'est cette rigidité qui en fait la structure des réseaux minimaux, des hiérarchies, et des arbres de parcours eux-mêmes : les pères d'un BFS forment précisément un arbre à $n-1$ arêtes.)

import random

def distance_moyenne(G: dict, nb_sources: int = 50) -> float:
    total, compte = 0, 0
    for s in random.sample(list(G), nb_sources):   # échantillon de sources
        d = distances(G, s)                         # un BFS complet : O(n + m)
        total += sum(d.values())
        compte += len(d) - 1                        # sans la source elle-même
    return total / compte

Mesures typiques : sur le cycle régulier ($n=1000$, voisins à distance $\le 2$), un tour peut coûter jusqu'à $250$ pas — distance moyenne $\approx 125$. Après recâblage de $1\%$ des arêtes seulement : distance moyenne $\approx 25$ — division par cinq pour un changement d'un centième (et chaque point de recâblage supplémentaire l'écrase davantage) ! Les quelques arêtes longues servent de raccourcis planétaires que le parcours en largeur emprunte aussitôt. C'est le phénomène du petit monde : les réseaux réels (sociaux, web, neuronaux) mêlent un fort voisinage local et de rares liens lointains, d'où les fameux « six degrés de séparation » — des distances moyennes minuscules dans des graphes géants. (Méthodologiquement : la distance moyenne exacte exigerait $n$ parcours, $O(n(n+m))$ — l'échantillonnage de sources en donne une estimation honnête pour un centième du prix, et la validation consiste à vérifier la stabilité quand on double l'échantillon : les techniques du chapitre 4 — simulation, estimation, contrôle — appliquées aux graphes ; les vrais mesureurs du web ne font pas autrement.)