Parcourir un graphe en largeur : BFS

Explorer des couches de distance

Le sommet de départ a distance zéro. Ses voisins ont distance un s’ils ne sont pas déjà connus. Les voisins encore inconnus de ces derniers ont distance deux, et ainsi de suite. Cette progression par couches explique le nom parcours en largeur.

Prenons les liaisons A-B, A-C, B-D, B-E et C-E, ainsi qu’un sommet isolé F. Depuis A, B et C sont à distance un ; D et E sont à distance deux. F n’a pas de distance finie depuis A. Une distance de zéro ne doit donc pas être utilisée pour signifier « inaccessible », puisque zéro décrit déjà le départ.

La file conserve le bon ordre

On place le départ dans une file et on le marque découvert. Tant que la file n’est pas vide, on retire son premier sommet u. Pour chaque voisin v encore inconnu, on fixe distance[v]=distance[u]+1, on enregistre son prédécesseur u et on ajoute v en fin de file.

Le marquage se fait lors de l’ajout, pas seulement lors du retrait. Sinon un même sommet voisin de plusieurs sommets en attente pourrait être ajouté plusieurs fois. Dans l’exemple, E est voisin de B et C : une seule découverte doit suffire, avec un prédécesseur défini par l’ordre des voisins.

La frontière est la file des sommets découverts mais pas encore traités. Elle ne contient pas tout l’historique du parcours. L’ensemble des découvertes, lui, conserve aussi les sommets déjà sortis. Un sommet absent de la file peut donc être encore inconnu ou avoir été complètement traité : il faut distinguer ces situations.

Cette implémentation renvoie les distances et les parents pour les sommets atteints. Le dictionnaire des distances sert aussi de mémoire des découvertes. Le graphe doit contenir une entrée pour chaque sommet, même isolé.

from collections import deque

def largeur(graphe, depart):
    file = deque([depart])
    distance = {depart: 0}
    parent = {depart: None}
    while file:
        u = file.popleft()
        for v in graphe[u]:
            if v not in distance:
                distance[v] = distance[u] + 1
                parent[v] = u
                file.append(v)
    return distance, parent

Retrouver un chemin sans conserver tous les chemins

Pour reconstruire un chemin de A à E, on suit les prédécesseurs en sens inverse. Si E a été découvert depuis B et B depuis A, la remontée donne E,B,A. Il suffit ensuite d’inverser cette liste pour obtenir A,B,E.

Un autre ordre de voisins peut découvrir E depuis C et produire A,C,E. Les deux chemins ont la même longueur minimale. L’arbre des prédécesseurs est une sélection parmi les possibilités, pas une liste de toutes les routes du graphe. Pour le départ, le prédécesseur peut être marqué absent afin d’arrêter la remontée.

Comprendre la garantie et sa limite

La file traite les sommets par distances non décroissantes. Lorsqu’un sommet est découvert pour la première fois à distance d, aucun chemin plus court n’a été oublié : ses couches précédentes ont déjà été explorées. C’est cette propriété qui justifie le minimum du nombre d’arêtes.

La garantie ne porte pas automatiquement sur des coûts pondérés. Deux arêtes coûteuses peuvent être moins intéressantes que trois arêtes peu coûteuses. Il faut alors un algorithme adapté aux poids. Avec des listes d’adjacence, BFS examine chaque sommet atteint et ses voisins, pour un coût de l’ordre du nombre de sommets plus celui des arêtes examinées.

Exemple suivi : le moment où une distance devient connue

Au départ A est découvert à distance zéro et la file contient A. Après traitement de A, B et C sont découverts à distance un : file [B,C]. Après traitement de B, D et E reçoivent distance deux et parent B : file [C,D,E]. E est déjà connu alors qu’il n’a pas encore été traité. Le traitement de C ne doit pas le remettre dans la file ni remplacer son parent dans cette variante.

Pourquoi cette distance deux est-elle minimale ? Si E avait été voisin du départ, il aurait été découvert pendant la première étape. Il ne l’a pas été. Il possède maintenant un chemin de deux arêtes via B ; aucun chemin de longueur inférieure ne reste à examiner. L’ordre des voisins peut choisir B ou C comme parent de E, mais tous ces parents possibles donnent une distance identique. La distance minimale peut être unique alors que le chemin ne l’est pas.

Exemple suivi : reconstruire et traiter les absences

Avec les parents E←B←A, partez de E et ajoutez successivement E, B, A dans une liste. A possède un marqueur sans parent, qui arrête la remontée. Inversez ensuite cette liste pour afficher A-B-E. Sa longueur en sommets vaut trois ; sa distance en arêtes vaut deux. Pour une destination égale au départ, la liste contient seulement A et la distance vaut zéro.

Pour F, aucun parent n’a été défini. Tant que le parcours n’est pas terminé, cela signifie seulement « pas encore découvert ». Une fois la file vide après exploration de la composante de A, on peut conclure que F est inaccessible depuis A. Ne remontez pas des parents absents et n’attribuez pas zéro à cette impossibilité. L’atelier conserve le terme « inconnue » pendant la progression ; votre justification d’inaccessibilité doit s’appuyer sur la fin effective de l’exploration.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Marquer seulement après le retrait.

Un sommet peut être ajouté plusieurs fois avant ce retrait.

Confondre plus court en sauts et plus faible coût.

BFS ignore les poids dans cette version.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2026 · Métropole · Jour 1 : Recto-Verso : jouer avec XOR et chercher la victoire dans un graphe
• Bac 2026 · Métropole · Jour 2 : Covoiturage : requêtes SQL, files et point de rendez-vous
• Bac 2026 · Antilles-Guyane · Jour 2 : Réseaux : route minimale, chemin pondéré et mémoire des prédécesseurs
• Bac 2025 · Métropole · Remplacement jour2 - 10 septembre 2025 : Commandes SQL et itinéraires de livraison

Le prochain pas

• Chercher des chemins et détecter des cycles
• Tables de routage et protocole RIP

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.