ITSkillsCenter
Développement Web

Implémenter le parcours BFS sur un graphe en Python

15 دقائق للقراءة

Tout ce qui ressemble à un réseau — pages web, comptes amis, villes reliées par des routes, paquets dépendant d’autres paquets — se modélise comme un graphe. Le parcours en largeur, ou BFS pour breadth-first search, est l’algorithme fondamental qui visite tous les sommets d’un graphe couche par couche, en partant d’un sommet source. Il sert à compter les degrés de séparation, à trouver le plus court chemin en nombre d’arêtes, à explorer un labyrinthe, ou à détecter une composante connexe. Ce tutoriel construit une représentation simple d’un graphe en Python, implémente BFS de zéro avec une deque, et bâtit la version qui reconstitue le chemin entre deux sommets.

Pour la vue d’ensemble des structures de données et des algorithmes, lire d’abord le guide principal Algorithmes et structures de données : repères 2026 pour devs.

Prérequis

  • Python 3.10 ou plus récent
  • Connaître les dictionnaires Python, les ensembles (set) et les listes
  • Avoir lu, idéalement, le tutoriel Coder une table de hachage en Python de cette série pour comprendre pourquoi le dictionnaire est la bonne structure pour la liste d’adjacence
  • Niveau attendu : intermédiaire
  • Temps estimé : 50 minutes pour suivre, 90 minutes avec les variantes

Étape 1 — Modéliser un graphe en Python

Un graphe est un ensemble de sommets reliés par des arêtes. Pour le représenter en mémoire, on a deux options principales : la matrice d’adjacence, un tableau V × V de booléens où la case (i, j) vaut True si i et j sont reliés ; et la liste d’adjacence, un dictionnaire qui à chaque sommet associe la liste de ses voisins. La matrice est simple mais dévore O(V²) de mémoire, ce qui devient prohibitif au-delà de quelques milliers de sommets. La liste d’adjacence ne stocke que ce qui existe vraiment — O(V + E) — et reste compacte tant que le graphe n’est pas dense.

En pratique, on choisit presque toujours la liste d’adjacence pour les graphes du monde réel. Un réseau social a quelques milliards d’utilisateurs mais chaque utilisateur a au mieux quelques milliers de connexions — le graphe est creux. Une matrice serait monstrueuse, une liste d’adjacence tient sans peine. La classe Python ci-dessous utilise un dictionnaire qui, à chaque sommet, mappe une liste de voisins. Les sommets peuvent être n’importe quel type hachable : chaînes, entiers, tuples.

class Graph:
    def __init__(self):
        self._adj = {}

    def add_vertex(self, v):
        if v not in self._adj:
            self._adj[v] = []

    def add_edge(self, u, v):
        """Ajoute une arête non orientée entre u et v."""
        self.add_vertex(u)
        self.add_vertex(v)
        self._adj[u].append(v)
        self._adj[v].append(u)

    def neighbors(self, v):
        return self._adj.get(v, [])

    def __contains__(self, v):
        return v in self._adj

    def __iter__(self):
        return iter(self._adj)

    def __len__(self):
        return len(self._adj)

L’opération add_edge ajoute la relation dans les deux sens parce qu’on modélise un graphe non orienté. Pour un graphe orienté (relations à sens unique : suivi sur Twitter, dépendance de paquet, lien hypertexte), il suffirait de retirer le second append. Tester l’API : g = Graph(); g.add_edge("A", "B"); g.add_edge("B", "C"); print(g.neighbors("B")) doit afficher ['A', 'C']. La complexité de l’ajout d’une arête est O(1) en moyenne, parce que dict et list.append sont en O(1) amorti.

Étape 2 — Construire un graphe de test

Avant d’écrire BFS, on prépare un petit graphe sur lequel on pourra valider visuellement le résultat. On choisit une topologie qui force l’algorithme à traiter plusieurs branches : six sommets nommés A à F, avec quelques arêtes qui créent des chemins multiples. C’est le genre de cas test qui permet de vérifier non seulement que l’algorithme finit, mais qu’il visite les sommets dans le bon ordre et qu’il n’oublie personne.

g = Graph()
edges = [
    ("A", "B"), ("A", "C"),
    ("B", "D"), ("B", "E"),
    ("C", "E"),
    ("E", "F"),
]
for u, v in edges:
    g.add_edge(u, v)

Représenté à plat, le graphe ressemble à : A est relié à B et C ; B est relié à A, D, E ; C est relié à A et E ; D à B uniquement ; E à B, C, F ; F à E uniquement. Il y a deux chemins distincts entre A et E (par B ou par C), ce qui sert à vérifier que BFS trouve bien le plus court — deux arêtes — sans se laisser piéger par celui qu’il rencontre en premier. Le sommet F est terminal et ne se visite qu’à la dernière vague.

Étape 3 — Implémenter BFS

BFS exploite trois structures auxiliaires : un ensemble visited qui mémorise les sommets déjà rencontrés (pour éviter les boucles infinies sur les graphes avec cycles), une file queue qui stocke les sommets à explorer ensuite (FIFO — premier entré, premier sorti, pour préserver l’ordre par couches), et une liste order qui retient l’ordre de visite. La file s’implémente en Python avec collections.deque, qui offre popleft() en O(1) là où list.pop(0) serait en O(n).

from collections import deque

def bfs(graph, start):
    """Parcours en largeur depuis start. Renvoie l'ordre de visite."""
    if start not in graph:
        return []
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Le déroulement sur le graphe de l’étape 2 avec start=A donne : on part avec visited={A}, queue=[A]. On retire A, on l’ajoute à order, ses voisins B et C n’ont pas été visités donc on les marque et les empile : visited={A,B,C}, queue=[B,C]. Vague suivante : on retire B (premier entré), on découvre D et E, on les empile : queue=[C,D,E]. Puis C, qui ne révèle rien de nouveau (E déjà visité). Puis D (rien). Puis E, qui découvre F. Puis F. Résultat final : ['A', 'B', 'C', 'D', 'E', 'F'] — les sommets sont visités exactement par couches de distance croissante depuis A.

Étape 4 — Calculer le plus court chemin

BFS ne trouve pas seulement les sommets accessibles : il garantit que la distance, en nombre d’arêtes, est minimale. Cette propriété tient parce que l’algorithme visite tous les sommets à distance 1 avant de toucher ceux à distance 2, etc. Pour reconstituer le chemin, on enregistre pour chaque sommet le sommet par lequel on l’a découvert — c’est le tableau parent. Une fois la cible atteinte, on remonte la chaîne des parents jusqu’à la source.

def shortest_path_bfs(graph, start, target):
    """Plus court chemin en nombre d'arêtes. None si non joignable."""
    if start not in graph or target not in graph:
        return None
    if start == target:
        return [start]
    visited = {start}
    queue = deque([start])
    parent = {start: None}
    while queue:
        node = queue.popleft()
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                if neighbor == target:
                    return _reconstruct_path(parent, target)
                queue.append(neighbor)
    return None

def _reconstruct_path(parent, target):
    path = []
    cur = target
    while cur is not None:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    return path

Sur le graphe de l’étape 2, shortest_path_bfs(g, "A", "F") renvoie ['A', 'B', 'E', 'F'] — trois arêtes, ce qui est bien le plus court. La reconstruction part de F, lit parent[F]=E, parent[E]=B, parent[B]=A, parent[A]=None, ce qui donne F→E→B→A, qu’on inverse pour obtenir le bon ordre. Notez qu’on aurait aussi pu passer par C : A→C→E→F est de longueur 3 également. BFS renvoie celui qu’il a découvert en premier, ce qui dépend de l’ordre des voisins dans la liste d’adjacence. Pour le plus court chemin pondéré (avec des coûts différents par arête), il faut Dijkstra, pas BFS.

Étape 5 — Calculer toutes les distances depuis une source

Une variante utile renvoie la distance de chaque sommet à la source, pas seulement vers une cible donnée. Le code est presque identique au BFS de base, sauf qu’on remplace l’ordre de visite par un dictionnaire de distances. C’est l’algorithme qu’on utilise pour les degrés de séparation sur un réseau social, ou pour calculer les distances dans un labyrinthe à grille (où les sommets sont les cases libres et les arêtes relient les cases adjacentes).

def distances_from(graph, start):
    """Distance (en arêtes) de chaque sommet accessible à start."""
    if start not in graph:
        return {}
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph.neighbors(node):
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

Sur le graphe de l’étape 2 avec start=A, on obtient {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}. Les distances correspondent exactement à ce qu’on lit visuellement sur le diagramme. Si un sommet n’apparaît pas dans le dictionnaire renvoyé, c’est qu’il n’est pas joignable depuis la source — il appartient à une autre composante connexe du graphe. Cette propriété fait de BFS l’outil naturel pour énumérer les composantes connexes : on lance BFS depuis chaque sommet non encore visité, et chaque exécution révèle une composante.

Étape 6 — Vérification

Un test de bout en bout vérifie le parcours, le plus court chemin, et les distances sur le graphe préparé. On ajoute un cas isolé (un sommet sans arête) pour valider la gestion des sommets inaccessibles, et un cas où start n’existe pas dans le graphe.

if __name__ == "__main__":
    g = Graph()
    edges = [("A","B"),("A","C"),("B","D"),("B","E"),("C","E"),("E","F")]
    for u, v in edges:
        g.add_edge(u, v)
    g.add_vertex("Z")  # sommet isolé

    # Parcours
    visited_order = bfs(g, "A")
    assert set(visited_order) == {"A", "B", "C", "D", "E", "F"}
    assert visited_order[0] == "A"

    # Plus court chemin
    path = shortest_path_bfs(g, "A", "F")
    assert path == ["A", "B", "E", "F"] or path == ["A", "C", "E", "F"]
    assert shortest_path_bfs(g, "A", "Z") is None
    assert shortest_path_bfs(g, "A", "A") == ["A"]

    # Distances
    dist = distances_from(g, "A")
    assert dist == {"A": 0, "B": 1, "C": 1, "D": 2, "E": 2, "F": 3}

    # Sommet inexistant
    assert bfs(g, "INCONNU") == []

    print("Tous les tests passent.")

Lancez python bfs.py et vous devez voir Tous les tests passent.. Si une assertion échoue, le test indique précisément ce qui est faux. Le cas shortest_path_bfs(g, "A", "Z") renvoie None parce que Z est isolé : on l’a ajouté comme sommet mais sans aucune arête, donc aucun parcours depuis A ne peut l’atteindre. La gestion correcte de ce cas est ce qui distingue une implémentation propre d’une implémentation qui plante à la première composante déconnectée.

Erreurs fréquentes

ErreurCauseSolution
Boucle infinie sur un graphe avec cyclesPas de jeu visited, ou marquage après dépilement au lieu de marquage à l’enfilementMarquer visited.add(neighbor) au moment où on l’empile, pas quand on le retire
BFS très lent avec list.pop(0)list.pop(0) est en O(n), ce qui rend le parcours global O(V × n)Utiliser collections.deque et popleft() qui est en O(1)
Plus court chemin incorrect avec poidsBFS suppose toutes les arêtes de coût 1Pour des arêtes pondérées, utiliser Dijkstra (avec heapq)
KeyError en parcoursVoisin référencé qu’on n’a pas ajouté comme sommetSoit utiliser graph.neighbors(node) qui renvoie [] par défaut, soit ajouter explicitement les sommets
Distances erronées sur graphe orientéadd_edge qui ajoute dans les deux sens alors que la relation est unidirectionnelleDistinguer la classe pour graphes orientés et celle pour graphes non orientés

BFS contre DFS : quand utiliser lequel

Le parcours en profondeur (DFS) explore aussi systématiquement, mais en suivant chaque branche jusqu’au bout avant de remonter. La différence d’implémentation tient à une seule structure : DFS utilise une pile (LIFO) à la place de la file, ou tout simplement la récursion. Le résultat fonctionnel est différent : DFS plonge en profondeur, BFS ratisse en largeur. Les deux ont la même complexité O(V + E) sur une liste d’adjacence, mais ils ne servent pas aux mêmes problèmes.

BFS est l’outil pour le plus court chemin non pondéré, les distances en arêtes, le calcul de niveaux dans une hiérarchie. DFS est l’outil pour la détection de cycles, le tri topologique d’un DAG, la recherche de composantes fortement connexes (algorithmes de Tarjan ou Kosaraju). Si vous écrivez un crawler web qui doit prioriser les pages les plus proches du point de départ, c’est BFS ; si vous résolvez un Sudoku ou explorez un arbre de jeux, c’est DFS avec backtracking. Avoir les deux en tête, et savoir quand basculer, fait partie de l’outillage de base.

Au-delà : Dijkstra et A*

Quand les arêtes ont des poids différents (distance kilométrique, latence réseau, coût financier), BFS ne donne plus le plus court chemin. L’algorithme de Dijkstra étend l’idée en remplaçant la file FIFO par une file de priorité (min-heap), ce qui permet d’explorer toujours le sommet de coût total le plus faible. Sa complexité avec un tas binaire (le module heapq de Python) est en O((V + E) log V). C’est l’algorithme derrière Google Maps, dans une version très optimisée avec préférences hiérarchiques.

L’algorithme A* va plus loin en ajoutant une heuristique qui estime la distance restante jusqu’à la cible, ce qui guide la recherche vers le but plutôt que d’explorer dans toutes les directions. Sur des grilles 2D (jeux vidéo, robotique), A* avec heuristique de Manhattan ou euclidienne explore des dizaines de fois moins de sommets que Dijkstra pur. Mais A* nécessite une heuristique admissible (ne surestime jamais), ce qui restreint son usage à des domaines où la géométrie aide.

Cas d’usage concrets dans le métier

Les développeurs sous-estiment la fréquence à laquelle ils manipulent des graphes sans le nommer. Le DOM d’une page HTML est un arbre, donc un graphe particulier — tout outil qui le parcourt (jQuery, querySelectorAll, scrapers) fait du BFS ou du DFS sans le dire. Le système de fichiers est un arbre, et la commande find de Unix exécute un DFS. Les dépendances de paquets npm, pip ou cargo forment un graphe orienté acyclique, et l’algorithme qui détermine l’ordre d’installation est un tri topologique — lui-même bâti sur DFS. Comprendre BFS et DFS, c’est lire ces outils et leurs comportements avec les bons mots.

Côté applicatif, BFS résout des problèmes qu’on rencontre en pratique : un labyrinthe à grille modélisable comme un graphe où chaque case libre est un sommet et chaque déplacement vers une case voisine une arête, le calcul du nombre de degrés de séparation entre deux profils LinkedIn ou Facebook, le crawling d’un site web où l’on veut explorer en priorité les pages les plus proches de la racine, ou encore la propagation d’une infection ou d’une rumeur dans un réseau social. À chaque fois, l’invariant est le même : on veut visiter par couches en partant d’une source, et on veut s’arrêter à une distance maximale ou à une cible donnée.

Performance et limites pratiques

BFS est en O(V + E) en temps et O(V) en mémoire pour la file et l’ensemble visited. Sur un graphe de 10 millions de sommets et 100 millions d’arêtes (taille typique d’un réseau social moyen), une exécution Python pure prend de l’ordre de 30 à 60 secondes — ce qui est gérable pour des analyses ponctuelles, mais inacceptable en latence d’API. Pour les vrais réseaux, on passe en C++ (graphes BGL), en Rust (petgraph) ou on délègue à une base de données graphe (Neo4j, ArangoDB) qui implémente BFS en interne avec des indices optimisés.

Une autre limite pratique concerne la mémoire. Sur un graphe énorme dont la liste d’adjacence ne tient pas en RAM, BFS classique échoue. Les variantes « external memory BFS » lisent et écrivent par blocs sur disque, en regroupant les sommets par couche pour limiter les accès aléatoires. Les frameworks comme Apache Giraph ou Pregel de Google distribuent BFS sur plusieurs machines en se basant sur le modèle « think like a vertex » : chaque sommet calcule localement son état et envoie des messages à ses voisins à chaque super-étape. Ces architectures dépassent largement le cadre de ce tutoriel mais valent d’être connues comme horizon.

Tutoriels suivants

Pour aller plus loin

#algorithmes #cluster-algo-ds #cluster-satellite #python #structures-de-donnees
Sponsoriser ce contenu

Cet emplacement est à vous

Position premium en fin d'article — c'est l'instant où les lecteurs sont le plus engagés. Réservez cet espace pour votre marque, votre formation ou votre offre.

Recevoir nos tarifs
Publicité