Algorithmes Python

Le parcours en largeur (BFS) en Python

Dans cette leçon, vous allez parcourir un graphe niveau par niveau avec le parcours en largeur et une file deque.

  • Intermédiaire
  • 3 min de lecture
  • 1 exemple exécutable

Introduction

Le problème

Combien d'étapes faut-il pour aller d'une personne à une autre dans un réseau social, ou d'une case d'un labyrinthe à la sortie ? Le parcours en largeur explore par cercles de plus en plus éloignés du départ. La première fois qu'il atteint un nœud, c'est donc par un plus court chemin.

Imaginez-le ainsi

Le parcours en largeur, c'est comme des ronds dans l'eau. Jetez une pierre au point de départ : l'onde atteint d'abord tout ce qui est à un pas, puis tout ce qui est à deux pas, et ainsi de suite. Rien n'est touché tant que tout ce qui est plus proche n'a pas été atteint.

Des ronds dans l'eau au code
queue = deque(["A"])🪨 Jeter la pierre en A
node = queue.popleft()🌊 Prendre le nœud suivant par ordre de distance
if neighbor not in visited:🔎 Pas encore atteint ?
queue.append(neighbor)➕ L'ajouter au cercle suivant
Les nœuds les plus proches d'abord, grâce à une file.
En une phrase

Le parcours en largeur (BFS) visite un graphe niveau par niveau depuis un nœud de départ, à l'aide d'une file, et trouve ainsi les plus courts chemins dans les graphes sans poids.

Points clés

  1. queue contient les nœuds en attente d'exploration, les plus anciens d'abord.
  2. visited enregistre les nœuds déjà découverts : aucun n'est ajouté deux fois, et un cycle ne peut pas faire tourner le parcours sans fin.
  3. node = queue.popleft() prend le nœud suivant ; ses voisins non visités rejoignent l'arrière de la file.
  4. order montre A, puis ses voisins B et C, puis D et E un niveau plus loin.

Quand l’utiliser ?

  • Les plus courts chemins dans les graphes, grilles et labyrinthes sans poids.
  • Les degrés de séparation dans les réseaux sociaux.
  • Les robots d'indexation web et la recherche de tout ce qui est atteignable depuis un point de départ.

Quand s'en passer

  • Les arêtes ont des coûts différents, comme des distances routières : utilisez l'algorithme de Dijkstra.
  • Vous devez explorer un chemin en entier avant les autres, comme pour le retour arrière : utilisez le parcours en profondeur.

Visualisation de Le parcours en largeur (BFS) en Python

O(V + E)

Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.

Code d’exemple

Exécuter le code →
main.py
from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []

while queue:
    node = queue.popleft()
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

print(order)
Obtenir un bouton Run pour cet exemple

Résultat de l’exécution

['A', 'B', 'C', 'D', 'E']

Explication du code

La file queue contient les sommets en attente de visite, qui sortent dans l'ordre où ils sont entrés. L'ensemble visited mémorise les sommets déjà rencontrés pour ne pas visiter plusieurs fois le même sommet quand le graphe contient des cycles. L'ordre de visite est A, B, C, D, E, et la complexité est O(V + E), où V est le nombre de sommets et E le nombre d'arêtes.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices d’approfondissement

Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Marquer les nœuds visités trop tard

Si un nœud n'est marqué que lorsqu'on le sort de la file, il peut être ajouté de nombreuses fois.

Problème
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
Correction
for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

Leçon terminée ?

Marquez-la comme apprise pour suivre votre progression.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis