Visualiseur BFS vs DFS

Observe comment BFS et DFS explorent le même graphe différemment. BFS avance en largeur, DFS avance en profondeur.

Valeurs de départ — Visualiseur BFS vs DFS

Graphe prédéfini	Grille 4x4
Nœud de départ	0

Modifiez un réglage ci-dessus et les résultats sont recalculés.

Chargement de la simulation interactive...

BFS ne trouve le plus court chemin que si toutes les arêtes coûtent pareil 🖖

On choisit d’ordinaire BFS parce qu’il renvoie le chemin le plus court. Cette garantie est plus étroite qu’il n’y paraît : elle tient parce que BFS traite chaque arête comme un pas, si bien qu’en atteignant un sommet pour la première fois, il y est forcément arrivé par le moins de sauts possible. Ajoutez de vrais coûts — distances routières, frais de correspondance, latence — et la garantie s’évanouit. BFS répondra toujours avec assurance, et il aura tort : un chemin de deux arêtes coûteuses peut facilement dépasser un chemin de cinq arêtes bon marché. L’algorithme de Dijkstra est la réparation, et il est presque exactement ceci : BFS où la file ordinaire est remplacée par une file de priorité.

Même carte, deux façons de voyager 🖖

En les lançant côte à côte, on remarque une chose : elles visitent exactement les mêmes nœuds et les mêmes arêtes, mais dans un ordre différent. Le parcours en largeur (BFS) explore tout le voisinage courant avant d'aller plus loin, il doit donc mémoriser chaque nœud en attente sur la frontière. Le parcours en profondeur (DFS) s'engage sur une branche et ne suit que le chemin en cours. À retenir : privilégiez le BFS quand la réponse est sans doute proche, et le DFS quand le graphe est profond et que la mémoire doit rester réduite.

Les deux algorithmes sont nés dans des labyrinthes 🖖

Bien avant les ordinateurs, le DFS existait comme une règle pour parcourir les labyrinthes, publiée par le mathématicien français Charles Pierre Trémaux au XIX^e siècle. Le BFS est arrivé bien plus tard : Edward F. Moore l'a réinventé dans un article de 1959 intitulé littéralement The Shortest Path Through a Maze, et Konrad Zuse l'avait déjà esquissé en 1945. Deux piliers de l'informatique, tous deux conçus au départ pour sortir d'un labyrinthe.

PARCOURS DE GRAPHE — QUEL ORDRE VOUS FAUT-IL, ET À QUEL COÛT ?

Dans quel cas de parcours êtes-vous ?

BFS et DFS visitent les mêmes sommets et diffèrent par une ligne de code : une file au lieu d’une pile. Tout le reste en découle. La file s’étend en anneaux : la première fois que BFS atteint un sommet, il y est venu par un chemin comptant le moins d’arêtes. La pile plonge : DFS atteint l’extrémité plus tôt, mais par aucune route particulière. Le bon choix dépend de la question — et de la forme du graphe, qui décide de ce que chacun coûte.

Il vous faut le moins d’arêtes — BFS, car il visite par couches de distance FIFO ⇒ min |E|

Un arbre — parcours par niveaux contre préfixe, et le coût mémoire s’inverse BFS: O(w), DFS: O(d)

Une chaîne — les deux ordres coïncident et le choix cesse d’importer deg ≤ 2 ⇒ BFS = DFS

Tout n’est pas atteignable — un seul sommet de départ ne suffit pas c(G) > 1

Il vous faut le moins d’arêtes — BFS, car il visite par couches de distance

Ce que vous savez: Un graphe non pondéré et une question de plus court chemin. BFS visite tout ce qui est à distance 1, puis tout ce qui est à distance 2 : la première arrivée sur un sommet emprunte donc un plus court chemin.

Règle: FIFO ⇒ min |E|

Exemple résolu: Sur la grille 4×4 depuis le sommet 0, BFS visite 0, 1, 4, 2, 5, 8, 3, 6, 9, 12, … — un front d’onde diagonal. DFS visite 0, 1, 2, 3, 7, 6, 5, 4, … et n’atteint le sommet 4 qu’à sa huitième étape.

Ouvrir ce cas: Grille 4x4

Il vous faut le moins d’arêtes — BFS, car il visite par couches de distance. BFS balaie vers l’extérieur par couches de distance ; DFS serpente d’abord dans un couloir. Un graphe non pondéré et une question de plus court chemin. BFS visite tout ce qui est à distance 1, puis tout ce qui est à distance 2 : la première arrivée sur un sommet emprunte donc un plus court chemin. — BFS balaie vers l’extérieur par couches de distance ; DFS serpente d’abord dans un couloir.

Un arbre — parcours par niveaux contre préfixe, et le coût mémoire s’inverse

Ce que vous savez: Dans un arbre les deux ordres ont un nom : BFS est le parcours par niveaux, DFS le parcours préfixe. Tous deux visitent les 15 sommets ; ce qui change, c’est la quantité à retenir en même temps.

Règle: BFS: O(w), DFS: O(d)

Exemple résolu: BFS donne 0, 1, 2, 3, …, 14 — niveau après niveau. DFS donne 0, 1, 3, 7, 8, 4, 9, 10, 2, … — d’abord le long de l’épine gauche. File maximale 8, pile maximale 4.

Ouvrir ce cas: Arbre binaire

Un arbre — parcours par niveaux contre préfixe, et le coût mémoire s’inverse. Le parcours par niveaux remplit chaque rangée avant de descendre ; le préfixe court jusqu’à une feuille puis remonte. Dans un arbre les deux ordres ont un nom : BFS est le parcours par niveaux, DFS le parcours préfixe. Tous deux visitent les 15 sommets ; ce qui change, c’est la quantité à retenir en même temps. — Le parcours par niveaux remplit chaque rangée avant de descendre ; le préfixe court jusqu’à une feuille puis remonte.

Une chaîne — les deux ordres coïncident et le choix cesse d’importer

Ce que vous savez: Chaque sommet a exactement un voisin non visité : il n’y a qu’une façon d’avancer. BFS et DFS produisent la même suite et ne gardent qu’un sommet à la fois.

Règle: deg ≤ 2 ⇒ BFS = DFS

Exemple résolu: Sur la chaîne de 12 sommets, tous deux visitent 0, 1, 2, …, 11 dans cet ordre, et les deux fronts restent de taille 1 du début à la fin.

Ouvrir ce cas: Longue chaîne

Une chaîne — les deux ordres coïncident et le choix cesse d’importer. Sans branchement, les deux parcours suivent la même ligne dans le même ordre. Chaque sommet a exactement un voisin non visité : il n’y a qu’une façon d’avancer. BFS et DFS produisent la même suite et ne gardent qu’un sommet à la fois. — Sans branchement, les deux parcours suivent la même ligne dans le même ordre.

Tout n’est pas atteignable — un seul sommet de départ ne suffit pas

Ce que vous savez: Le graphe est en morceaux. Lancé depuis un sommet, l’un ou l’autre parcours ne visite que la composante à laquelle ce sommet appartient, puis s’arrête.

Règle: c(G) > 1

Exemple résolu: Depuis le sommet 0 du graphe à 10 sommets, BFS et DFS visitent chacun exactement 4 sommets et s’arrêtent. Les sommets 4, 5, 6, 7, 8 et 9 ne sont jamais touchés.

Ouvrir ce cas: Déconnecté

Tout n’est pas atteignable — un seul sommet de départ ne suffit pas. Quatre sommets atteignables et six non : un départ explore une composante, pas davantage. Le graphe est en morceaux. Lancé depuis un sommet, l’un ou l’autre parcours ne visite que la composante à laquelle ce sommet appartient, puis s’arrête. — Quatre sommets atteignables et six non : un départ explore une composante, pas davantage.

Références (2)

Insight block 3 — BFS as a maze algorithm: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.
Trémaux's rule, as it was actually published: É. Lucas, Récréations mathématiques, vol. 1. Gauthier-Villars, Paris, 1882 — Lucas credits the maze-walking procedure to Charles Pierre Trémaux.

Problème entièrement résolu

Un parcours d'un labyrinthe contenant 16 nœuds et 16 arêtes 5 étapes
Le labyrinthe comprend 16 nœuds reliés par 16 arêtes. Calculez combien de nœuds sont atteints par un parcours débutant au nœud 0, et à quelle distance se trouve le nœud 15 du nœud 0. Il s'agit de l'état Couloir du labyrinthe avec le nœud de départ 0.
1. Représentez le labyrinthe sous forme de liste d'adjacence avant de faire quoi que ce soit d'autre. Le nœud 4 mérite une attention particulière : aucune arête ne le touche, son degré est donc 0 et aucun parcours débutant ailleurs ne pourra jamais l'atteindre.
  
  $0 : 11 : 0, 2, 52 : 1, 33 : 24 : \emptyset 5 : 1, 6, 96 : 5, 7, 107 : 6, 118 : 9, 12 9 : 5, 8, 1010 : 6, 9, 1411 : 7, 15 12 : 8, 1313 : 12, 1414 : 10, 1315 : 11$
2. Le parcours en largeur classe ce qu'il peut atteindre par couches, la couche k regroupant tout ce qui est rencontré pour la première fois depuis la couche k − 1. Leur construction relève de la fermeture plutôt que du cheminement — on termine entièrement une couche avant d'ouvrir la suivante, et aucun nœud n'apparaît deux fois.
  
  $L_{0} L_{3} L_{6} = {0} = {3, 6, 9} = {13, 15} L_{1} L_{4} = {1} = {7, 8, 10} L_{2} L_{5} = {2, 5} = {11, 12, 14}$
3. Additionnez les tailles des couches. Le parcours atteint 15 nœuds, soit un de moins que les 16 que contient le graphe, et c'est pourquoi le compteur d'étapes s'arrête un rang en dessous du nombre de nœuds.
  
  $1 + 1 + 2 + 3 + 3 + 3 + 2 = 15, n = 16, de g (4) = 0$
4. Le nœud 15 apparaît pour la première fois dans la couche 6, et le numéro d'une couche représente une distance : un nœud n'est ajouté à la file que depuis un nœud situé une couche au-dessus, de sorte que rien dans la couche 6 ne peut être atteint en moins de 6 arêtes. Le trajet 0-1-5-6-7-11-15 en atteint 6, la borne est donc exacte.
  
  $15 \in L_{6} ⟹ d (0, 15) = 6 : 0 \to 1 \to 5 \to 6 \to 7 \to 11 \to 15$
5. Le parcours en profondeur ne conserve aucun invariant de ce type. Supposons qu’au sommet 1, le parcours choisisse 5 avant 2, puis 9 avant 6 au sommet 5, et enfin 8 avant 10 au sommet 9. Chacun de ces choix entre voisins non visités est valide, mais le parcours s’engage alors dans le long couloir et ne revient sur ses pas qu’une fois arrivé dans une impasse. Il atteint le sommet 15 à l’autre extrémité d’un chemin de 12 arêtes, parfaitement valable pour répondre à la question de l’accessibilité.
  
  $0 \to 1 \to 5 \to 9 \to 8 \to 12 \to 13 \to 14 \to 10 \to 6 \to 7 \to 11 \to 15 ⟹ ℓ = 12$
Réponse

Le nœud 15 se trouve à 6 arêtes du départ, et un parcours en profondeur peut vous fournir un trajet de 12 arêtes pour arriver au même endroit. Le facteur 2 n'est pas le point le plus intéressant ; l'origine même d'un raccourci l'est en revanche. La composante accessible compte 15 nœuds, donc tout arbre couvrant de celle-ci utilise 14 arêtes — et le labyrinthe en compte 16, ce qui signifie qu'exactement 2 arêtes sont superflues. Supprimez ces 2 arêtes et ce qui reste est un arbre, où il existe exactement un chemin entre n'importe quelle paire de nœuds ; les deux panneaux s'accorderaient alors sur chaque distance et ne différeraient que par l'ordre de leur parcours. Tout désaccord sur les distances entre eux découle de ces 2 arêtes supplémentaires. C'est également la raison pour laquelle le parcours en profondeur est l'option la plus économique lorsqu'il s'agit seulement de savoir si un nœud est accessible, et la mauvaise dès lors qu'il s'agit de savoir à quelle distance.

$∣ E ∣ - (∣ V ∣ - 1) = 16 - (15 - 1) = 2$

Par l’équipe 42Math · Mis à jour 2026-07-27

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

Grille 4x4 - Grille 4×4 : BFS explore couche par couche
Couloir de labyrinthe - Corridor de labyrinthe
Graphe en étoile - Neuf branches, chaque nœud étant à un saut du centre. Le parcours en profondeur n'a nulle part où s'enfoncer, il renvoie donc le même ordre que le parcours en largeur.
Longue chaîne - Douze nœuds en ligne : les ordres correspondent à nouveau, mais ici chaque algorithme ne conserve qu'un seul nœud à la fois, contre neuf pour l'étoile.
Arbre binaire - Arbre binaire : DFS va en profondeur avant d'aller en largeur
Déconnecté - Deux carrés et deux nœuds isolés. Un parcours depuis le nœud 0 en atteint 4 sur les 10, et aucune recherche ne permet de trouver le reste.
Graphe dense - Graphe dense : beaucoup d'arêtes, ordres similaires