Que sont les algorithmes BFS et DFS, et quand choisir chacun d’eux ?

BFS et DFS sont des algorithmes de parcours de graphe qui trouvent systématiquement les sommets accessibles depuis un sommet de départ. BFS s’étend niveau par niveau à partir des sommets proches, ce qui le rend adapté lorsque vous avez besoin d’un chemin comportant le nombre minimal d’arêtes dans un graphe non pondéré. DFS suit une branche aussi loin que possible avant de revenir en arrière ; il sert donc de base à des problèmes tels que l’analyse structurelle, la détection de cycles et le tri topologique. Aucun n’est systématiquement meilleur que l’autre : le choix dépend du critère appliqué au chemin et de l’objectif du graphe. ocw.mit.edu↗algs4.cs.princeton.edu↗

Que trouvent BFS et DFS lors d’un parcours de graphe ?

Un graphe est une structure relationnelle composée de sommets et d’arêtes. Les sommets représentent des entités telles que des personnes, des villes, des pages web ou des tâches, tandis que les arêtes représentent les connexions entre elles, telles que des amitiés, des routes, des liens ou des relations de prérequis. L’ensemble des sommets est noté $V$, et l’ensemble des arêtes $E$.

Lorsque les arêtes n’ont pas de direction, le graphe est non orienté. Par exemple, une amitié réciproque peut généralement être considérée comme bidirectionnelle. À l’inverse, des relations telles que A suit B ou la tâche A doit être terminée avant la tâche B forment un graphe orienté. Dans un graphe orienté, vous ne pouvez vous déplacer que dans le sens d’une flèche ; vous ne pouvez pas automatiquement vous déplacer dans le sens opposé. ocw.mit.edu↗

La question la plus élémentaire d’un parcours de graphe est : « Quels sommets sont accessibles depuis un point de départ $s$ ? » En répondant à cette question, BFS et DFS peuvent également enregistrer des informations supplémentaires, par exemple si un sommet a été visité, le chemin par lequel chaque sommet a été atteint pour la première fois et l’ordre de parcours. Toutefois, un parcours commencé depuis un sommet ne traite que la partie réellement accessible depuis ce sommet. Il ne visite pas nécessairement tous les sommets du graphe. ocw.mit.edu↗

Un arbre est également un type de graphe. Par conséquent, BFS et DFS peuvent être utilisés pour des problèmes qui ressemblent à des arbres, comme des hiérarchies de dossiers ou des organigrammes. Il est toutefois important de se rappeler qu’un graphe général peut contenir des cycles qui reviennent vers un sommet, ainsi que plusieurs chemins vers un même sommet. Appliquer directement à un graphe général une implémentation conçue uniquement pour le parcours d’arbres peut entraîner des visites en double.

Comment BFS explore-t-il d’abord les sommets proches ?

BFS signifie Breadth-First Search, ou parcours en largeur. Il trouve d’abord les sommets accessibles depuis le point de départ par une arête, puis les sommets qui nécessitent deux arêtes, puis trois, en étendant la zone de recherche dans cet ordre. Ici, la distance n’est ni une distance physique ni un coût : c’est le nombre d’arêtes à parcourir depuis le point de départ. algs4.cs.princeton.edu↗

BFS utilise généralement une file pour cela. Une file est une structure de données FIFO (First In, First Out), ce qui signifie que le premier élément ajouté est le premier retiré. Placez le sommet de départ dans la file et marquez-le comme visité, puis retirez un sommet à l’avant de la file. Marquez comme visités tous les voisins non découverts de ce sommet et ajoutez-les à l’arrière de la file. Répétez l’opération jusqu’à ce que la file soit vide. Comme les sommets proches découverts précédemment sont traités en premier, l’expansion niveau par niveau est préservée. gh.cp-algorithms.com↗algs4.cs.princeton.edu↗

Par exemple, supposons qu’en partant de A, vous découvriez les voisins B et C de A. Lorsque BFS traite B, il découvre les voisins de B ; il traite ensuite C et découvre les voisins de C. Même si un sommet découvert depuis B est plus profond, C, qui a déjà été placé dans la file au même niveau, est traité avant lui ou juste après. L’ordre exact entre B et C peut varier selon l’ordre de stockage des sommets adjacents.

La clé de BFS est de marquer un sommet comme visité dès qu’il est découvert. Si vous retardez ce marquage jusqu’à son retrait de la file, deux sommets peuvent chacun découvrir le même voisin et l’insérer plusieurs fois dans la file. Dans un BFS classique, marquer un nouveau voisin comme découvert au moment même où il est ajouté à la file est plus simple et plus sûr.

Dans quelles conditions BFS fournit-il un plus court chemin ?

BFS est souvent choisi parce que, dans un graphe non pondéré, il trouve un chemin présentant le nombre minimal d’arêtes du sommet de départ vers chaque sommet accessible. Il examine tous les sommets à une étape du départ avant d’examiner les sommets à deux étapes ; un chemin comportant moins d’arêtes que le chemin qui découvre un sommet pour la première fois ne peut donc pas apparaître ultérieurement. Si vous enregistrez le sommet précédent comme parent lorsque chaque sommet est découvert pour la première fois pendant BFS, ces pointeurs parent forment un arbre des plus courts chemins. algs4.cs.princeton.edu↗

Pour reconstruire un chemin, suivez les pointeurs parent à rebours depuis le sommet cible jusqu’au sommet de départ, puis inversez l’ordre. Par exemple, si parent[D] = B et parent[B] = A, le chemin découvert de A à D est A → B → D. Utilisez un marqueur distinct pour indiquer que le sommet de départ n’a pas de parent.

Toutefois, interpréter « le plus court » de manière trop large conduit à des erreurs. BFS garantit le nombre minimal d’arêtes uniquement lorsque toutes les arêtes peuvent être considérées comme ayant le même coût. Si les routes ont des durées de trajet différentes ou les vols des tarifs différents, un chemin utilisant deux arêtes peut être moins cher ou plus rapide qu’un chemin n’en utilisant qu’une. Dans ce cas, BFS standard n’est pas un algorithme de plus court chemin par coût. Selon les propriétés des poids, envisagez des méthodes dédiées aux graphes pondérés, comme l’algorithme de Dijkstra ou l’algorithme de Bellman-Ford. algs4.cs.princeton.edu↗

BFS convient donc bien à des problèmes tels que « Combien de degrés de séparation y a-t-il entre deux amis ? » ou « Combien de mouvements faut-il pour atteindre un point dans une grille lorsque se déplacer d’une case vers le haut, le bas, la gauche ou la droite compte comme un mouvement ? » En revanche, si l’objectif est le temps minimal ou le coût minimal, vérifiez d’abord si les poids des arêtes sont réellement égaux.

Pourquoi DFS va-t-il en profondeur avant de revenir en arrière ?

DFS signifie Depth-First Search, ou parcours en profondeur. Depuis le sommet courant, il choisit un voisin non visité et continue à avancer jusqu’à avoir exploré une branche aussi profondément que possible. Lorsqu’il atteint une impasse, il revient au sommet précédent et cherche un autre voisin qui n’a pas encore été exploré. Ce processus de retour est également appelé retour sur trace. ocw.mit.edu↗

DFS est facile à implémenter avec des appels récursifs. Lorsqu’on entre dans un sommet, on le marque d’abord comme visité, puis on appelle la même fonction de parcours pour chaque voisin non visité de ce sommet. Lorsqu’un appel récursif se termine, le contrôle revient naturellement au point qui l’a appelé, ce qui exprime le déroulement consistant à aller en profondeur puis à revenir en arrière.

La récursion n’est pas la seule possibilité. DFS peut aussi être implémenté de manière itérative avec une pile explicite. Une pile est une structure de données LIFO (Last In, First Out), ce qui signifie que le dernier élément ajouté est le premier retiré. En retirant d’abord le sommet découvert le plus récemment, vous pouvez produire un comportement en profondeur. Dans une implémentation récursive, la pile d’appels du programme joue implicitement ce rôle. ocw.mit.edu↗gh.cp-algorithms.com↗

Les pointeurs parent créés par DFS peuvent également montrer un chemin depuis le sommet de départ jusqu’à un sommet. Cependant, ce chemin n’est pas garanti d’avoir le nombre minimal d’arêtes. Comme DFS suit aussi loin que possible la première branche choisie, il peut ne découvrir un chemin plus court dans une autre branche que plus tard. ocw.mit.edu↗

Quels types d’analyse structurelle utilisent DFS ?

DFS montre sa valeur lorsqu’il s’agit d’analyser la structure du graphe plutôt que de simplement vérifier l’accessibilité. La recherche de composantes connexes en est un exemple représentatif. Dans un graphe non orienté, exécuter DFS une fois depuis n’importe quel sommet non visité trouve tous les sommets qui y sont reliés comme un groupe. Lancer à nouveau DFS depuis un sommet non visité restant trouve un autre groupe.

La détection de cycles est une autre application courante de DFS. Un cycle est une structure dans laquelle suivre les arêtes peut vous ramener au point de départ ou à un sommet déjà présent sur le chemin courant. Dans un graphe orienté, vous pouvez détecter un cycle en distinguant le cas où vous rencontrez un sommet qui se trouve déjà sur le chemin récursif courant. C’est pourquoi il faut distinguer un sommet qui a simplement été visité une fois d’un sommet qui se trouve actuellement sur le chemin de parcours.

Le tri topologique ordonne des dépendances orientées, comme les relations de prérequis entre des tâches, selon un ordre donné. Il n’est possible que dans un graphe orienté acyclique, ou DAG. Un DAG est un graphe orienté sans cycle qui revient à son point de départ en suivant le sens des arêtes. Si un cycle existe, une contradiction apparaît — par exemple, B doit être terminé avant A et A doit être terminé avant B — donc aucun ordre linéaire ne peut satisfaire toutes les arêtes. Une méthode qui utilise l’ordre de fin de DFS constitue l’une des bases du tri topologique. algs4.cs.princeton.edu↗

La recherche de composantes fortement connexes est également un sujet important fondé sur DFS. Une composante fortement connexe est un ensemble de sommets d’un graphe orienté dans lequel deux sommets quelconques d’un même groupe peuvent s’atteindre mutuellement. Toutefois, ce problème ne se résout pas par un seul DFS simple : il exige une construction algorithmique qui utilise l’ordre de parcours et le sens des arêtes. algs4.cs.princeton.edu↗

Quels problèmes surviennent sans marqueurs de visite ?

Dans un graphe général, un tableau ou un ensemble de sommets visités n’est pas facultatif ; il est essentiel à la terminaison et à la correction. Par exemple, si A et B sont reliés, vous pouvez aller de A à B puis revenir de B à A. Sans vérifier l’état de visite, DFS peut alterner récursivement entre A et B indéfiniment, et BFS peut placer le même sommet plusieurs fois dans la file. ocw.mit.edu↗

Le terme « visité » peut être subdivisé légèrement différemment selon l’implémentation. Dans BFS, un sommet est généralement marqué comme « découvert » au moment où il est ajouté à la file. Dans DFS, il est courant de marquer un sommet comme visité immédiatement à l’entrée dans sa fonction. Une analyse plus élaborée des graphes orientés peut distinguer un état non visité, un état en cours d’exploration et un état terminé.

Le principe consistant à ne visiter chaque sommet qu’une seule fois est directement lié à l’efficacité du parcours. Si vous ne développez pas les sommets déjà traités, alors, avec des listes d’adjacence, vous examinez chaque sommet et chaque arête seulement un nombre limité de fois. De plus, si vous attribuez un pointeur parent uniquement lorsqu’un sommet est découvert pour la première fois, le chemin qui a découvert ce sommet en premier est clair.

Pour parcourir tout un graphe, vous avez besoin d’une boucle externe. Examinez chaque sommet à tour de rôle et, chaque fois que vous en trouvez un qui n’a pas encore été visité, démarrez un nouveau BFS ou DFS depuis celui-ci. Dans un graphe non orienté, cela produit un parcours par composante connexe. Dans un graphe orienté, cela traite successivement les zones accessibles dans le sens des arêtes choisi. ocw.mit.edu↗

Pourquoi la complexité temporelle dépend-elle de la représentation du graphe ?

La complexité temporelle de BFS et DFS est souvent donnée comme $O(\lvert V \rvert + \lvert E \rvert)$. Il s’agit de l’analyse standard lorsqu’on utilise des listes d’adjacence. Une liste d’adjacence stocke, pour chaque sommet, la liste de ses voisins directement connectés. Avec des marqueurs de visite, chaque sommet est traité une fois et les arêtes sont vérifiées lors du balayage des listes de voisins ; le travail total est donc proportionnel au nombre de sommets plus le nombre d’arêtes. ocw.mit.edu↗

L’espace supplémentaire est généralement de $O(\lvert V \rvert)$. Cela inclut le tableau des sommets visités, le tableau des parents, ainsi que la file de BFS ou la pile de DFS. Pour un DFS récursif, la pile d’appels requise par la profondeur de récursion est également comprise dans l’espace supplémentaire. Il est utile de distinguer l’espace utilisé pour stocker le graphe lui-même de l’espace additionnel utilisé par l’algorithme de parcours. ocw.mit.edu↗

Une matrice d’adjacence stocke l’existence d’une arête pour chaque paire de sommets dans une table. Pour trouver les voisins d’un sommet, vous pouvez devoir examiner chaque sommet possible. Par conséquent, BFS ou DFS utilisant une matrice d’adjacence peut généralement prendre $O(\lvert V \rvert^2)$ en temps. Pour les graphes creux comportant peu d’arêtes, les listes d’adjacence sont particulièrement efficaces, car elles ne parcourent que les voisins réellement connectés. ocw.mit.edu↗

La notation de complexité décrit comment l’utilisation des ressources tend à croître lorsque la taille de l’entrée augmente. Le temps d’exécution réel est aussi influencé par les identifiants de sommets, l’implémentation des listes d’adjacence, la disposition en mémoire et la taille de la partie accessible depuis le point de départ du parcours. Néanmoins, lors du choix d’un algorithme, il est judicieux de vérifier d’abord si le graphe est creux et comment il est représenté.

L’ordre réel de visite de BFS ou DFS est-il fixe ?

Non. BFS suit le principe consistant à traiter d’abord les niveaux les plus proches, et DFS suit le principe consistant à explorer profondément la branche courante ; mais le sommet visité en premier au sein d’un même niveau, ou la branche explorée en premier parmi plusieurs voisins, dépend de l’ordre de stockage des sommets adjacents. gh.cp-algorithms.com↗gh.cp-algorithms.com↗

Par exemple, si la liste des voisins de A est ordonnée B, C, BFS découvre généralement B en premier. Si la liste devient C, B, C peut être découvert en premier. Cette différence peut avoir un effet plus important dans DFS. Si le premier voisin choisi change, la branche explorée en profondeur elle-même change, de même que l’arbre de parcours et les chemins DFS créés par les pointeurs parent.

Ce fait est important lors de l’évaluation du résultat d’un algorithme. Si un problème exige « l’ordre de visite lexicographiquement premier », vous devez trier les listes d’adjacence ou définir une règle de priorité. En revanche, si vous avez seulement besoin de l’accessibilité, du nombre de composantes connexes ou des distances minimales en nombre d’arêtes, l’ordre détaillé au sein d’un même niveau ou d’une même profondeur peut ne pas être central au résultat.

En particulier, lors de l’implémentation itérative de DFS avec une pile, l’ordre dans lequel les voisins sont empilés peut être l’inverse de l’ordre dans lequel ils sont effectivement retirés. Si vous voulez obtenir le même ordre de visite qu’une implémentation récursive utilisant un ordre donné de liste d’adjacence, vous devez ajuster intentionnellement le sens dans lequel les voisins sont ajoutés à la pile. Il ne s’agit pas d’une définition différente de DFS, mais d’une différence d’implémentation causée par le comportement LIFO.

Quelles sont les idées reçues et les erreurs courantes ?

La première est l’idée reçue selon laquelle BFS résout tout type de problème de plus court chemin. Comme indiqué précédemment, BFS garantit le nombre minimal d’arêtes dans un graphe non pondéré. Si les poids diffèrent, un déplacement n’a pas nécessairement la même valeur qu’un autre ; le modèle du problème lui-même change donc. algs4.cs.princeton.edu↗algs4.cs.princeton.edu↗

La deuxième est l’hypothèse selon laquelle DFS utilise toujours moins de mémoire que BFS. En incluant les tableaux de sommets visités et l’état de parcours, les deux algorithmes peuvent généralement utiliser $O(\lvert V \rvert)$ d’espace supplémentaire. La taille maximale de la file ou de la pile peut différer pour certaines formes de graphes et certaines implémentations, mais la seule complexité asymptotique n’établit pas un avantage inconditionnel pour l’un ou l’autre. ocw.mit.edu↗

La troisième est la croyance qu’un DFS récursif est sûr pour toute entrée. Dans un graphe à très grande profondeur, la profondeur de récursion devient également importante. Vous devez tenir compte de la limite de pile d’appels du langage et de l’environnement d’exécution ; dans de tels cas, une implémentation itérative avec une pile explicite peut être plus pratique. Il est également important de comprendre que la pile d’appels récursive fait partie de l’espace supplémentaire de DFS. ocw.mit.edu↗

La quatrième consiste à traiter un graphe orienté comme s’il était non orienté. L’existence d’une arête de A vers B ne signifie pas que vous pouvez aller de B vers A. Lors du stockage de l’entrée dans des listes d’adjacence, un graphe non orienté ajoute généralement une arête à la liste des deux sommets, tandis qu’un graphe orienté ne l’ajoute qu’à la liste du sommet source. Cette différence modifie le sens de l’accessibilité, de la connectivité et des cycles. ocw.mit.edu↗

La cinquième consiste à prendre un résultat de parcours pour un chemin correct unique. Lorsque plusieurs chemins ont le même nombre minimal d’arêtes, BFS en enregistre un par l’intermédiaire des pointeurs parent. DFS peut également produire des chemins différents selon l’ordre des voisins. Si le chemin lui-même exige une priorité, des règles de tri ou des conditions supplémentaires doivent être précisées dans le problème.

Quels critères utiliser pour choisir selon le problème ?

Il est préférable de commencer par formuler l’objectif. Si la question demande seulement : « Peut-on l’atteindre depuis le point de départ ? », BFS et DFS sont tous deux possibles, et vous pouvez choisir selon l’environnement d’implémentation et l’analyse nécessaire ensuite. Si vous avez besoin du nombre minimal d’arêtes, par exemple « Combien de déplacements identiques sont nécessaires pour arriver ? », BFS est le choix naturel. Si vous devez suivre un chemin en profondeur tout en analysant la structure, ou si le moment où vous revenez en arrière est important, DFS est probablement approprié.

Ensuite, vérifiez ce que signifient les arêtes. Déterminez si chaque déplacement a le même coût ou si des poids tels que le temps, la distance ou le coût interviennent. Si des poids existent, n’appliquez pas directement la propriété de plus court chemin de BFS. Vérifiez également à l’avance si le graphe est orienté, si des cycles sont possibles et si vous devez examiner l’ensemble du graphe. ocw.mit.edu↗algs4.cs.princeton.edu↗

Les critères de sélection peuvent être résumés comme suit.

Enfin, prenez en compte la taille et la représentation de l’entrée. Pour un graphe creux, les listes d’adjacence et l’analyse standard en $O(\lvert V \rvert + \lvert E \rvert)$ de BFS et DFS conviennent bien. Dans les environnements où la profondeur de récursion peut poser problème, envisagez DFS itératif. Si l’ordre de visite influence l’évaluation ou les règles métier, l’ordre des listes d’adjacence fait également partie de la conception.

Conclusion : les objectifs et les conditions du parcours comptent plus que les noms

BFS et DFS sont des stratégies différentes pour parcourir complètement un graphe. BFS utilise une file pour s’étendre depuis les sommets proches et a l’avantage de fournir des chemins comportant un nombre minimal d’arêtes dans les graphes non pondérés. DFS utilise la récursion ou une pile pour explorer une branche en profondeur et revenir en arrière ; il constitue la base de nombreuses méthodes qui exploitent la structure des graphes, notamment les composantes connexes, les cycles et le tri topologique dans les DAG. ocw.mit.edu↗algs4.cs.princeton.edu↗

Les deux exigent des marqueurs de visite et ont généralement la même complexité temporelle asymptotique lorsqu’ils utilisent des listes d’adjacence. Ainsi, la clé du choix entre eux n’est pas une simple étiquette comme la vitesse, mais ce qui définit un plus court chemin, si les arêtes sont pondérées, comment le sens et les cycles doivent être interprétés, et si tout le graphe doit être traité. Distinguer d’abord ces conditions vous permet d’utiliser BFS et DFS dans le bon objectif.