Français
Menu

Parcours en largeur vs parcours en profondeur (BFS vs DFS) : ordre de visite, structure de données, plus courts chemins, mémoire, usages

Ce sont deux façons de visiter tous les sommets d’un graphe ou d’un arbre en suivant ses arêtes. Le parcours en largeur (BFS) s’étend par ordre de distance : il visite d’abord tous les sommets à une arête du départ, puis ceux à deux arêtes, et ainsi de suite. Le parcours en profondeur (DFS) suit un chemin aussi loin que possible, puis, arrivé à une impasse, revient en arrière et essaie un autre chemin. Le BFS s’implémente avec une file et le DFS avec une pile ou par récursion ; sur un graphe stocké en listes d’adjacence, tous deux visitent tout en un temps proportionnel au nombre de sommets plus le nombre d’arêtes. Le BFS est le choix habituel pour les plus courts chemins dans un graphe non pondéré, et le DFS pour explorer exhaustivement tous les chemins ou détecter des cycles.

CritèreParcours en largeur (BFS)Parcours en profondeur (DFS)
Ordre de visiteLes plus proches d’abord (le moins d’arêtes depuis le départ), en s’étendant couche par coucheDescend loin le long d’un chemin, revient en arrière à une impasse et passe au chemin suivant
Structure de données utiliséeFile (premier entré, premier sorti)Pile (dernier entré, premier sorti) ou appels récursifs
Plus courts cheminsDans un graphe non pondéré, le nombre d’arêtes au moment où un sommet est atteint pour la première fois est sa distance minimale au départNon garantis : un sommet peut être atteint d’abord par un détour
Complexité temporelle (V sommets, E arêtes)O(V + E) avec des listes d’adjacence, O(V²) avec une matrice d’adjacenceIdentique au BFS : O(V + E) avec des listes d’adjacence, O(V²) avec une matrice d’adjacence
MémoireLes sommets à visiter sont conservés dans la file ; avec beaucoup de branches, toute une couche de sommets y séjourne à la fois, si bien qu’elle devient grandeEn version récursive, seuls les sommets du chemin courant sont nécessaires : la mémoire croît avec la profondeur du chemin ; une recherche très profonde peut faire déborder la pile d’appels
Garantie de trouver une solutionToujours trouvée si le nombre de sommets est fini ; même si l’espace de recherche croît sans limite, les solutions peu profondes sont trouvées en premierToujours trouvée dans un graphe fini si les sommets visités sont mémorisés ; lorsque les chemins peuvent s’approfondir sans limite, il peut continuer à descendre un même chemin sans jamais revenir
Ordre de parcours d’un arbreParcours par niveaux (niveau par niveau depuis la racine, de gauche à droite)Parcours préfixe, infixe et postfixe
Usages typiquesPlus courts chemins dans un graphe non pondéré, nombre minimal de coups dans un labyrinthe, nombre de sauts atteints dans un réseauRecherche exhaustive dans les labyrinthes et les casse-têtes (backtracking), recherche des composantes connexes et des cycles, tri topologique

Les valeurs indiquées sont des ordres de grandeur typiques et varient selon la génération de procédé et le produit.

Quand choisir l'un ou l'autre ?

Parcours en largeur
Lorsqu’on veut le nombre minimal d’étapes ou le plus court chemin dans un graphe non pondéré, ou examiner les sommets par ordre de proximité avec le départ. Pour les plus courts chemins avec des arêtes pondérées, on utilise l’algorithme de Dijkstra.
Parcours en profondeur
Lorsqu’on veut explorer exhaustivement tous les chemins ou toutes les combinaisons, trouver les composantes connexes ou les cycles, ou effectuer un tri topologique pour ordonner des tâches. Il s’écrit de façon compacte par récursion.

Questions fréquentes

Le BFS trouve-t-il les plus courts chemins quand les arêtes ont des poids ?

Non, car le chemin qui a le moins d’arêtes n’a pas forcément le plus petit poids total. Si les poids sont positifs ou nuls, on utilise l’algorithme de Dijkstra. Celui-ci remplace la file par une file de priorité qui retire d’abord le sommet le plus proche du départ, et peut être vu comme une extension du BFS aux graphes pondérés.

Faut-il écrire le DFS par récursion ou avec une pile explicite ?

La récursion est courte et lisible, mais dans des graphes très profonds, les appels imbriqués peuvent faire déborder la pile d’appels. L’écrire sous forme de boucle avec sa propre pile évite ce problème. Selon l’ordre dans lequel les voisins sont empilés, l’ordre de visite peut toutefois différer de la version récursive.

Que se passe-t-il si l’on ne mémorise pas les sommets visités ?

Dans un graphe qui contient des cycles, les mêmes sommets sont visités encore et encore. Avec le BFS, la file grossit sans limite, et avec le DFS, la recherche peut tourner indéfiniment autour du même cycle. Dans les deux méthodes, on marque donc les sommets visités (ou déjà ajoutés à la file ou à la pile) pour ne jamais les ajouter de nouveau.

Vérifier vos connaissances

Dans un graphe dont les arêtes n'ont pas de poids, on veut trouver le plus petit nombre d'arêtes entre un sommet de départ et chacun des autres sommets. Quelle association entre méthode de recherche et structure de données convient ?

  1. ALe parcours en largeur avec une file d'attente
  2. BLe parcours en profondeur avec une pile
  3. CLe parcours en largeur avec une pile
Afficher la réponse et l'explication

Réponse : A. Le parcours en largeur avec une file d'attente

Le parcours en largeur visite les sommets par ordre de distance : d'abord ceux qui sont à une arête du départ, puis ceux qui sont à deux arêtes, et ainsi de suite. Ajouter chaque sommet nouvellement découvert à l'arrière d'une file d'attente et prendre les sommets par l'avant préserve cet ordre « du plus proche au plus lointain » ; le nombre d'arêtes au moment où un sommet est atteint pour la première fois est donc le plus court. Le parcours en profondeur (par récursion ou avec une pile) avance le plus loin possible le long d'un chemin : il peut atteindre un sommet d'abord par un détour, et les distances les plus courtes ne sont pas garanties. Remplacer la file par une pile transforme le parcours en quelque chose de proche d'un parcours en profondeur.

Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Afficher la réponse et l'explication

Réponse : C. A, B, D, E, F, C

Depuis A, le parcours passe à B, puis à D, le premier voisin non visité de B. Le seul voisin de D, B, est déjà visité : le parcours revient donc à B et passe à E, puis de E au sommet non visité F, et de F à son voisin C. L'ordre est donc A, B, D, E, F, C. A, B, C, D, E, F est l'ordre du parcours en largeur, qui visite d'abord les sommets les plus proches. A, B, D, E, C, F revient en arrière depuis E sans aller au sommet non visité F : ce n'est donc pas un ordre de parcours en profondeur.

Quelle est une façon appropriée de stocker en mémoire un graphe creux, c'est-à-dire un graphe ayant peu d'arêtes par rapport à son nombre de sommets, comme un réseau routier d'environ 1 million de sommets et 3 millions d'arêtes ?

  1. AUne matrice d'adjacence : elle vérifie en O(1) si deux sommets sont reliés et occupe aussi le moins de mémoire
  2. BDes listes d'adjacence : la mémoire est proportionnelle au nombre de sommets plus le nombre d'arêtes, et elles conviennent pour suivre une à une les arêtes qui partent d'un sommet
  3. CUne matrice d'adjacence : sa mémoire n'est proportionnelle qu'au nombre d'arêtes
Afficher la réponse et l'explication

Réponse : B. Des listes d'adjacence : la mémoire est proportionnelle au nombre de sommets plus le nombre d'arêtes, et elles conviennent pour suivre une à une les arêtes qui partent d'un sommet

Une matrice d'adjacence utilise une table V × V pour V sommets : 1 million de sommets demandent donc 10¹² cases, soit environ 125 GB même à 1 bit par case. Les listes d'adjacence ne stockent que les voisins de chaque sommet : la mémoire est en O(V + E), seulement quelques millions d'entrées dans cet exemple. La matrice d'adjacence a l'avantage de tester l'existence d'une arête en O(1) et convient aux graphes denses ou aux graphes ayant peu de sommets. Pour les traitements qui suivent tour à tour les arêtes partant de chaque sommet, comme le parcours en largeur et l'algorithme de Dijkstra, les listes d'adjacence sont plus efficaces.

  1. Dans un graphe non orienté, les poids des arêtes (distances) sont S−A : 4, S−B : 1, A−B : 2, A−C : 1, B−C : 5, C−T : 3 et A−T : 6. Quelle réponse donne le plus court chemin de S à T trouvé par l'algorithme de Dijkstra et sa longueur ?
  2. On insère dans cet ordre les valeurs 50, 30, 70, 20, 40, 60, 80 dans un arbre binaire de recherche vide. Dans quel ordre les nœuds sont-ils visités quand on parcourt l'arbre dans l'ordre postfixe (sous-arbre gauche, sous-arbre droit, puis le nœud) ?

Questions d'entraînement sur Structures de données et algorithmes

Termes clés expliqués

Parcours en largeur (breadth-first search)
Méthode d'exploration d'un graphe ou d'un arbre qui visite les sommets par ordre de distance au départ : d'abord ceux qui sont à une arête, puis ceux qui sont à deux arêtes, et ainsi de suite. Elle s'implémente avec une file d'attente et, dans un graphe sans poids sur les arêtes, trouve le plus petit nombre d'arêtes entre le départ et chaque sommet. On l'abrège en BFS.
Parcours en profondeur (depth-first search)
Méthode d'exploration d'un graphe ou d'un arbre qui avance le plus loin possible le long d'un chemin et revient en arrière pour essayer un autre chemin quand elle atteint une impasse. Elle s'implémente par récursion ou avec une pile et sert à la résolution de labyrinthes, à la recherche de composantes connexes et de cycles, et au tri topologique. On l'abrège en DFS.
File d'attente
Structure de données FIFO (premier entré, premier sorti) dans laquelle l'élément ajouté en premier est retiré en premier. L'ajout à l'arrière s'appelle enqueue (enfilage) et le retrait à l'avant dequeue (défilage). Les files d'attente servent aux files de travaux en attente, à la transmission de données entre tâches et au parcours en largeur.
Pile (stack)
Structure de données LIFO (dernier entré, premier sorti) dans laquelle l'élément ajouté en dernier est retiré en premier. L'ajout d'un élément s'appelle push et son retrait pop. Les piles servent à gérer les adresses de retour et les variables locales lors des appels de fonction (pile d'appels), à évaluer les expressions en notation polonaise inverse et au parcours en profondeur.
Récursion (récursivité)
Le fait qu'une fonction s'appelle elle-même au cours de son propre traitement. Le problème est découpé en problèmes plus petits de même forme, et les appels s'arrêtent sur un cas qui n'est plus découpé (le cas de base). Chaque appel occupe de l'espace sur la pile, si bien qu'une récursion trop profonde provoque un débordement de pile. La récursion terminale, dans laquelle l'appel récursif est la dernière action de la fonction, peut être transformée en boucle.
Algorithme de Dijkstra
Algorithme qui trouve les plus courts chemins d'un sommet de départ vers tous les sommets d'un graphe dont les poids des arêtes sont supérieurs ou égaux à 0. Il fixe de façon répétée le sommet le plus proche dont la distance n'est pas encore définitive et met à jour les distances de ses voisins. Il ne fonctionne pas correctement avec des poids d'arêtes négatifs.
Complexité temporelle (notation grand O)
Description de la façon dont le travail (complexité temporelle) ou la mémoire (complexité spatiale) nécessaires à un algorithme croissent avec le nombre de données n. Elle s'écrit en notation grand O, par exemple O(n), O(n log n) ou O(n²), en omettant les facteurs constants et les termes de degré inférieur.

Comparatifs associés