02 — Le parcours en largeur (BFS)

Ce que tu vas apprendre

• Le principe du parcours en largeur, niveau par niveau
• Pourquoi il utilise une file et un ensemble de visités
• Comment il donne le plus court chemin non pondéré
• Sa complexité et ses usages

Prérequis

• 01 — Représenter un graphe
• La file (FIFO) de la série Structures de données

Le parcours en largeur (BFS, Breadth-First Search) explore un graphe par cercles concentriques : d'abord le sommet de départ, puis tous ses voisins directs, puis les voisins de ses voisins, et ainsi de suite. Cette progression par niveaux a une conséquence remarquable : BFS trouve le plus court chemin en nombre d'arêtes, sans effort supplémentaire. C'est l'algorithme à dégainer dès qu'on cherche « le moins d'étapes pour aller de X à Y ».

Le principe et la file

BFS s'appuie sur une file (FIFO, vue dans la série Structures de données). On y met le sommet de départ, puis on répète : on défile un sommet, on traite ses voisins non encore vus en les enfilant. Comme la file sert les sommets dans l'ordre où ils ont été découverts, on explore bien niveau par niveau.

Un point critique : il faut marquer les sommets déjà visités, sinon on tourne en rond dans les cycles. On utilise un Set pour ça (recherche en O(1), rappel de la série Complexité).

pythonfrom collections import deque

def bfs(graphe, depart):
    visites = {depart}
    file = deque([depart])
    ordre = []
    while file:
        sommet = file.popleft()       # défiler : O(1)
        ordre.append(sommet)
        for voisin in graphe[sommet]:
            if voisin not in visites:  # O(1) grâce au Set
                visites.add(voisin)
                file.append(voisin)    # enfiler : O(1)
    return ordre

On marque un sommet comme visité au moment de l'enfiler, pas au moment de le défiler. C'est une erreur classique : si on attend le défilement, un même sommet peut être enfilé plusieurs fois par différents voisins, ce qui fausse le parcours et dégrade les performances.

Le plus court chemin non pondéré

Voici la propriété qui rend BFS si utile. Parce qu'il explore par niveaux, la première fois qu'il atteint un sommet, c'est forcément par un chemin de longueur minimale en nombre d'arêtes. Il suffit de mémoriser, pour chaque sommet, par quel prédécesseur on l'a atteint, pour reconstruire le chemin.

pythondef plus_court_chemin(graphe, depart, arrivee):
    if depart == arrivee:
        return [depart]
    visites = {depart}
    file = deque([depart])
    predecesseur = {depart: None}
    while file:
        sommet = file.popleft()
        for voisin in graphe[sommet]:
            if voisin not in visites:
                visites.add(voisin)
                predecesseur[voisin] = sommet
                if voisin == arrivee:
                    return reconstruire(predecesseur, arrivee)
                file.append(voisin)
    return None  # arrivee inatteignable

def reconstruire(predecesseur, arrivee):
    chemin = []
    courant = arrivee
    while courant is not None:
        chemin.append(courant)
        courant = predecesseur[courant]
    return chemin[::-1]  # du départ à l'arrivée

Attention : cette propriété ne vaut que pour les graphes non pondérés (ou à poids égaux). Dès que les arêtes ont des poids différents, le chemin avec le moins d'arêtes n'est plus forcément le moins coûteux, et il faut Dijkstra (article 06).

Complexité

BFS visite chaque sommet une fois et examine chaque arête une fois (deux fois pour un graphe non orienté). Avec une liste d'adjacence, sa complexité est O(V + E) : linéaire en la taille du graphe. C'est optimal, on ne peut pas faire mieux que regarder chaque sommet et chaque arête. C'est aussi pourquoi la liste d'adjacence est préférée : avec une matrice, le parcours des voisins ferait grimper le coût à O(V²).

Les usages

• Plus court chemin non pondéré : nombre minimal d'étapes, degrés de séparation dans un réseau social (« à quelle distance suis-je de cette personne ? »).
• Plus proche d'abord : trouver le magasin, le serveur ou la ressource la plus proche en nombre de sauts.
• Parcours de grille : dans un labyrinthe ou une carte de jeu, BFS trouve le chemin le plus court entre deux cases (les cases sont les sommets, les déplacements les arêtes).
• Diffusion par niveaux : propagation, calcul de toutes les distances depuis une source.

BFS et son cousin le parcours en profondeur (article suivant) sont les deux briques de base sur lesquelles reposent presque tous les autres algorithmes de graphes. L'article suivant présente le parcours en profondeur, qui explore au plus loin avant de revenir, et ouvre la voie à la détection de cycle et au tri topologique.

Sources

• Moore, E. F. (1959). The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching. (Origine du BFS pour les chemins)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 22.2 "Breadth-First Search". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 4.1. Addison-Wesley.