BFS explore un graphe niveau par niveau, visitant tous les voisins d'un nœud avant d'aller plus profond. Elle utilise une queue et trouve le chemin le plus court (le moins d'arêtes) dans les graphes non pondérés.
L'idée
Commencez à une source, enfilez-la, puis répétez : défilez un nœud, visitez ses voisins non visités, et enfilez-les. Un ensemble visited empêche les revisites.
Exemple
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # FIFO: explore nearest first
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A') # -> ['A', 'B', 'C', 'D']
Complexité
- Temps : O(V + E) — chaque sommet et arête une fois.
- Espace : O(V) pour la queue et l'ensemble visité.
Quand l'utiliser / pièges
Utilisez BFS pour le chemin le plus court dans les graphes non pondérés, le parcours par niveaux, et la recherche de composantes connexes. Elle utilise plus de mémoire que DFS (toute une frontière à la fois). Tracez toujours visited sinon vous risquez de boucler à l'infini sur les cycles.
Pourquoi c'est important
BFS est l' algorithme pour les chemins les plus courts quand chaque arête compte pareillement — routage, crawling web, degrés de séparation dans les réseaux sociaux.
Sa structure basée sur une queue, niveau par niveau, est un motif de traversal fondamental.
Connaître BFS vs DFS vous permet de choisir le bon outil pour les problèmes d'accessibilité, de chemins et d'ordonnancement.