module · parcours de graphe · 12 min
BFS ou DFS ? Selon la structure auxiliaire.
Mêmes nœuds, mêmes arêtes, mais un ordre de visite radicalement différent. La file donne un parcours en largeur (BFS). La pile donne un parcours en profondeur (DFS).
file (FIFO)
A
tête à gauche, queue à droite
visités · ordre
aucun pour l'instant
étape
départ : on enfile A.
×2
défi · qui atteint la cible en premier ?
palier 1 / 4
Avec BFS depuis A, dérouler le parcours jusqu'à atteindre la cible G. BFS la visite forcément au plus court — combien d'arêtes au minimum ?
distance min = 3atelier piloté : toile · multi-chemins · BFS · départ A
Déroulez le parcours dans l'atelier (lecture / pas-à-pas) jusqu'à visiter G.
G visitée à l'étape 8 · distance min = 3 arêtes
à retenir
- BFS visite les voisins immédiats avant de descendre — il atteint toujours un nœud par le plus court chemin en nombre d'arêtes.
- DFS plonge le plus loin possible avant de remonter — utile pour détecter un cycle, parcourir un arbre, résoudre un labyrinthe.
- DFS peut atteindre une cible avant BFS quand il s'engage tôt dans la bonne branche profonde — mais sans aucune garantie de plus court chemin.
- Les deux ont la même complexité O(n + m) mais explorent dans un ordre totalement différent.
- Le BFS récursif n'existe pas naturellement ; le DFS, si — il utilise alors la pile d'appels du programme à la place d'une pile explicite.