Qu'est-ce que la recherche en largeur d'abord (BFS) ?

Question

IT Interview Practice · Accepted Answer

**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

```python
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.

L'idée

Exemple

Complexité

Quand l'utiliser / pièges

Pourquoi c'est important

Questions connexes