BFS et DFS sont les deux parcours de graphe à connaître en priorité. BFS explore un graphe par niveaux, tandis que DFS descend aussi loin que possible avant de revenir en arrière. En Python, BFS s’écrit naturellement avec collections.deque, et DFS avec une pile ou une fonction récursive.
Ces deux algorithmes servent à explorer un réseau, détecter des composantes, trouver un chemin, parcourir des dépendances ou préparer des algorithmes plus avancés comme Dijkstra, Prim, Kruskal ou A*.
La réponse courte
Utilisez BFS quand vous voulez explorer par distance croissante depuis un sommet de départ. Dans un graphe non pondéré, BFS trouve le chemin avec le plus petit nombre d’arêtes.
Utilisez DFS quand vous voulez explorer en profondeur : composantes connexes, parcours complet, détection de cycles, backtracking ou analyse de dépendances.
| Parcours | Structure | Usage typique | Complexité |
|---|---|---|---|
| BFS | file FIFO avec deque |
plus court chemin non pondéré, niveaux | O(V + E) |
| DFS | pile ou récursion | exploration profonde, composantes, cycles | O(V + E) |
V est le nombre de sommets et E le nombre d’arêtes.
Représenter un graphe en Python
La représentation la plus simple est un dictionnaire d’adjacence.
graphe = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": ["F"],
"F": [],
}
Chaque clé est un sommet. La liste associée contient ses voisins.
Cette représentation est lisible, rapide à parcourir et suffisante pour apprendre les principaux algorithmes de graphe.
BFS en Python avec deque
BFS signifie Breadth-First Search, ou parcours en largeur. Il visite d’abord les voisins directs, puis les voisins des voisins.
from collections import deque
def bfs(graphe, depart):
visites = {depart}
file = deque([depart])
ordre = []
while file:
sommet = file.popleft()
ordre.append(sommet)
for voisin in graphe[sommet]:
if voisin not in visites:
visites.add(voisin)
file.append(voisin)
return ordre
print(bfs(graphe, "A"))
Résultat possible :
['A', 'B', 'C', 'D', 'E', 'F']
La file garantit que les sommets sont traités par niveaux. C’est exactement ce qu’il faut pour trouver un plus court chemin dans un graphe non pondéré.
Trouver un chemin avec BFS
Pour retrouver le chemin, on mémorise le parent de chaque sommet.
from collections import deque
def chemin_bfs(graphe, depart, arrivee):
parents = {depart: None}
file = deque([depart])
while file:
sommet = file.popleft()
if sommet == arrivee:
break
for voisin in graphe[sommet]:
if voisin not in parents:
parents[voisin] = sommet
file.append(voisin)
if arrivee not in parents:
return None
chemin = []
courant = arrivee
while courant is not None:
chemin.append(courant)
courant = parents[courant]
return chemin[::-1]
print(chemin_bfs(graphe, "A", "F"))
BFS ne tient pas compte des poids. Si vos arêtes ont des coûts différents, utilisez plutôt Dijkstra ou A*.
DFS en Python avec une pile
DFS signifie Depth-First Search, ou parcours en profondeur. La version itérative utilise une pile.
def dfs_iteratif(graphe, depart):
visites = set()
pile = [depart]
ordre = []
while pile:
sommet = pile.pop()
if sommet in visites:
continue
visites.add(sommet)
ordre.append(sommet)
for voisin in reversed(graphe[sommet]):
if voisin not in visites:
pile.append(voisin)
return ordre
print(dfs_iteratif(graphe, "A"))
L’ordre exact dépend de l’ordre des voisins. C’est normal : DFS décrit une stratégie d’exploration, pas un ordre unique universel.
DFS récursif
La version récursive est très lisible.
def dfs_recursif(graphe, sommet, visites=None, ordre=None):
if visites is None:
visites = set()
if ordre is None:
ordre = []
visites.add(sommet)
ordre.append(sommet)
for voisin in graphe[sommet]:
if voisin not in visites:
dfs_recursif(graphe, voisin, visites, ordre)
return ordre
print(dfs_recursif(graphe, "A"))
Elle est pratique pour apprendre, mais attention aux graphes très profonds : Python limite la profondeur de récursion. Dans ce cas, la version itérative est plus sûre.
Quand choisir BFS ou DFS
| Situation | Choix recommandé |
|---|---|
| Plus court chemin dans un graphe non pondéré | BFS |
| Explorer des niveaux autour d’un sommet | BFS |
| Tester l’accessibilité | BFS ou DFS |
| Parcourir toutes les dépendances | DFS |
| Détecter des composantes | BFS ou DFS |
| Faire du backtracking | DFS |
| Graphe très profond | DFS itératif plutôt que récursif |
Pour un graphe pondéré, BFS n’est pas suffisant. Il faut passer à Dijkstra en Python ou à A* si vous avez une heuristique utile.
Erreurs fréquentes
La première erreur est d’oublier l’ensemble visites. Sans lui, un graphe avec cycle peut provoquer une boucle infinie.
La deuxième erreur est d’utiliser list.pop(0) pour BFS. Cette opération est coûteuse, car elle décale les éléments. Utilisez deque.popleft().
La troisième erreur est de croire que BFS donne un plus court chemin dans un graphe pondéré. Ce n’est vrai que si chaque arête a le même coût.
La quatrième erreur est de confondre sommet visité et sommet ajouté à la file. Pour BFS, on marque généralement un sommet comme visité au moment où on l’ajoute à la file, afin d’éviter les doublons.
Où continuer
BFS et DFS sont la base du cluster graphes. Pour replacer ces parcours dans une vision plus large, lisez :
- Algorithmes Python : tous les guides pour apprendre pas à pas
- Algorithmes de graphes en Python
- Complexité algorithmique en Python
- Algorithme de Prim en Python avec heapq
La règle à retenir : BFS explore par couches, DFS explore par profondeur. Si cette différence est claire, les algorithmes de graphe avancés deviennent beaucoup plus faciles à comprendre.
Références
- Documentation Python – collections.deque
- Documentation Python – structures de données
- Documentation Python – set
