Comment puis-je me rappeler quelles structures de données sont utilisées par DFS et BFS ?

Question

Je mélange toujours si j'utilise une pile ou une file d'attente pour DFS ou BFS. Quelqu'un peut-il s'il vous plaît fournir une intuition sur la façon de se rappeler quel algorithme utilise quelle structure de données ?

Answer 1

La file d'attente peut généralement être considérée comme horizontale dans la structure, c'est-à-dire que la largeur/largeur peut lui être attribuée - BFS, alors que

La pile est visualisée comme une structure verticale et a donc de la profondeur - DFS.

Answer 2

Dessinez un petit graphique sur un morceau de papier et pensez à l'ordre dans lequel les nœuds sont traités dans chaque implémentation. En quoi l'ordre dans lequel vous rencontrez les nœuds et l'ordre dans lequel vous traitez les nœuds diffèrent-ils entre les recherches ?

L'un d'eux utilise une pile (profondeur en premier) et l'autre une file d'attente (largeur en premier) (pour les implémentations non récursives, au moins).

Answer 3

Je m'en souviens en gardant Barbecue dans mon esprit. Le barbecue commence par un « B » et se termine par un son comme « q » d'où BFS -> Queue et les autres DFS -> stack.

Answer 4

BFS explore/traite d'abord les sommets les plus proches, puis s'éloigne de la source. Compte tenu de cela, vous souhaitez utiliser une structure de données qui, lorsqu'elle est interrogée, vous donne l'élément le plus ancien, en fonction de l'ordre dans lequel ils ont été insérés. Une file d'attente est ce dont vous avez besoin dans ce cas puisqu' il s'agit du premier entré, premier sorti(FIFO). Alors qu'un DFS explore autant que possible le long de chaque branche d'abord, puis entre parenthèses. Pour cela, une pile fonctionne mieux puisqu' elle est LIFO(last-in-first-out)

Answer 5

BFS utilise toujours la file d'attente, Dfs utilise la structure de données Stack. Comme nous l'avons expliqué précédemment, la DFS utilise le retour en arrière. Rappelez-vous que le retour arrière ne peut se faire que par Stack.