Français
Menu

Qu'est-ce que 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.

Nom japonais: 幅優先探索

« Parcours en largeur (breadth-first search) » apparaît dans 5 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Parcours en largeur (breadth-first search)

On ajoute dans cet ordre les éléments A, B et C à une file d'attente vide. Ensuite, on retire un élément, on ajoute D et on retire un élément, puis on ajoute E et on retire un élément. Dans quel ordre les éléments sont-ils retirés ?

  1. AA, B, C
  2. BC, D, E
  3. CC, B, A
Afficher la réponse et l'explication

Réponse : A. A, B, C

Une file d'attente est une structure FIFO (premier entré, premier sorti) : les éléments sont retirés dans l'ordre où ils ont été ajoutés. Après l'ajout de A, B et C, le premier retrait prend A. Même si D et E sont ensuite ajoutés à l'arrière, B et C, placés devant, sortent d'abord : l'ordre de retrait est donc A, B, C, et D et E restent dans la file. C, D, E serait l'ordre obtenu avec une pile (LIFO), qui retire à chaque fois l'élément ajouté le plus récemment. Les files servent pour les travaux d'impression, pour les files de messages qui transmettent des données entre tâches et pour le parcours en largeur.

Quand on parcourt un arbre binaire de recherche dans l'ordre infixe (sous-arbre gauche, puis le nœud, puis sous-arbre droit), dans quel ordre se présentent les valeurs des nœuds visités ? On suppose toutes les valeurs distinctes.

  1. ADans l'ordre croissant (la plus petite d'abord)
  2. BDans l'ordre où elles ont été insérées
  3. CPar proximité avec la racine (les moins profondes d'abord)
Afficher la réponse et l'explication

Réponse : A. Dans l'ordre croissant (la plus petite d'abord)

Dans un arbre binaire de recherche, pour chaque nœud, toutes les valeurs du sous-arbre gauche sont plus petites que celle du nœud et toutes celles du sous-arbre droit sont plus grandes. Visiter le sous-arbre gauche, le nœud puis le sous-arbre droit parcourt donc les valeurs de la plus petite à la plus grande : le résultat est dans l'ordre croissant. Visiter les nœuds par proximité avec la racine est un parcours en largeur (parcours par niveaux), qui avance niveau par niveau, de gauche à droite. L'ordre d'insertion influe sur la forme de l'arbre, mais ne correspond à l'ordre d'aucun de ces parcours.

« Parcours en largeur (breadth-first search) » dans les explications

Questions mentionnant « Parcours en largeur (breadth-first search) » (5)

  1. On ajoute dans cet ordre les éléments A, B et C à une file d'attente vide. Ensuite, on retire un élément, on ajoute D et on retire un élément, puis on ajoute E et on retire un élément. Dans quel ordre les éléments sont-ils retirés ?
  2. Quand on parcourt un arbre binaire de recherche dans l'ordre infixe (sous-arbre gauche, puis le nœud, puis sous-arbre droit), dans quel ordre se présentent les valeurs des nœuds visités ? On suppose toutes les valeurs distinctes.
  3. 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 ?
  4. 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 ?
  5. 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 ?

Termes associés

File d'attente Pile (stack) Parcours en profondeur (depth-first search) Récursion (récursivité) Arbre binaire de recherche (binary search tree) Algorithme de Dijkstra Algorithme glouton (greedy) Complexité temporelle (notation grand O) Liste chaînée (linked list) Programmation dynamique

Retour au glossaire