J'étais en train d'apprendre sur l'ampleur de la première recherche et une question m'est venue à l'esprit pourquoi BFS est appelé ainsi. Dans le livre Introduction to Algorithms de CLRS , j'ai lu la raison suivante:
La recherche en largeur d'abord est ainsi nommée car elle étend la frontière entre les sommets découverts et non découverts uniformément sur toute la largeur de la frontière.
Cependant, je ne suis pas en mesure de comprendre le sens de cette déclaration. Je suis confus au sujet de ce mot «frontière» et de l'étendue de cette frontière.
Alors, quelqu'un peut-il répondre à cette question d'une manière facile à comprendre pour un débutant comme moi?
graphs
graph-theory
shortest-path
graph-traversal
TheHungryCoder
la source
la source
Réponses:
Considérez la structure de données utilisée pour représenter la recherche. Dans un BFS, vous utilisez une file d'attente. Si vous rencontrez un nœud invisible, vous l'ajoutez à la file d'attente.
La «frontière» est l'ensemble de tous les nœuds de la structure de données de recherche. La file d'attente parcourra séquentiellement tous les nœuds de la frontière, itérant ainsi sur toute la largeur de la frontière. DFS fera toujours sortir l'état le plus récemment découvert de la pile, itérant ainsi toujours sur la partie la plus profonde de la frontière.
Considérez l'image ci-dessous. Remarquez comment le DFS va directement aux parties les plus profondes de l'arbre tandis que le BFS itère sur la largeur de chaque niveau.
Image ici
la source
a, la frontière esta. Lorsque vous avez découverta,b,c, la frontière estb,c. Lorsque vous avez découverta,b,c,d,e,f,g, la frontière estd,e,f,g. En d'autres termes, les nœuds qui ont été découverts et que nous n'avons pas encore recherchés.La citation que vous donnez dit "la frontière entre les sommets découverts et non découverts". Voilà donc la frontière dont parle l'auteur: la frontière entre les sommets découverts et non découverts. Vous avez des sommets que vous n'avez encore rien vus. Vous avez également des sommets pour lesquels vous avez tout vu. Et puis vous avez des sommets entre les deux. Ce sont des sommets que vous avez regardés, mais vous n'avez pas encore chargé tous leurs enfants. Telle est la frontière.
Le discute de ce sujet plus loin:
Ainsi, tous les sommets commencent en blanc (non découvert). Lorsqu'un nœud est découvert, il est de couleur grise (frontière). Lorsque tout ce qu'il désigne a été découvert, il est coloré en noir (complètement découvert). La frontière est l'ensemble des points qui ont été découverts, mais dont les enfants n'ont pas été découverts.
Supposons que vous cherchiez quelque chose sur le site Web. Vous accédez d'abord à la page principale. Supposons que ce soit étiqueté "animaux". La frontière est actuellement {"animaux"}. Vous parcourez la page principale et ne voyez pas ce que vous recherchez. Mais vous remarquez qu'il a des liens vers deux autres pages, "quadrupèdes" et "vers". Vous cliquez donc sur le lien "quadrupèdes". Maintenant, la frontière est {"animaux", "quadrupèdes"}. Vous regardez à travers les "quadrupèdes" et ne trouvez pas ce que vous cherchez. Qu'est ce que tu fais après? Vous pouvez soit rechercher des liens sur "quadrupèdes" et les suivre, soit revenir à "animaux" et cliquer sur le lien "vers". La première est une recherche en profondeur d'abord, et la seconde est une recherche en largeur d'abord.
"profondeur" se réfère au nombre de liens du nœud racine qu'il faut pour arriver à un nœud, tandis que "largeur" se réfère aux nœuds comme la même profondeur. Dans l'exemple ci-dessus, BFS commence par "animaux" et regarde d'abord tous les nœuds de profondeur un, donc il regarde d'abord les "quadrupèdes" et les "vers". Une fois qu'il a examiné tous les nœuds de profondeur 1, il étend la frontière à travers tous ces nœuds; c'est-à-dire qu'il examine les enfants de tous les nœuds de profondeur 1 avant de regarder l'un des enfants de nœuds de profondeur 2. Ainsi, par exemple, si l'un des liens de la page "quadrupèdes" est "primates", il examinera tous les liens de la page "vers" avant d'examiner les liens de la page "primates".
la source
Supposons que l'algorithme BFS soit exécuté à partir du sommet . Imaginez une vague qui sort d' (comme une vague d'eau ou un tsunami). Après un pas de temps, la vague aurait atteint tous les voisins d' . Après deux pas de temps, l'onde aurait atteint (ou "visité") tous les sommets qui sont à distance au plus de . Etc.a a a 2 a
À tout moment, la frontière de l'onde est exactement les sommets qui sont stockés dans la structure de données de file d'attente (ces sommets ont été visités mais pas encore explorés).
Ainsi, l'onde atteint initialement toute la "largeur" de tous les sommets qui sont à la distance 1 de . Après quelques pas de temps, la vague aurait couvert toute la largeur jusqu'à une certaine distance du point de départ .a a
L'ensemble des sommets à la distance de est appelé la ème couche dans la partition de distance du graphe par rapport au sommet . L'ensemble des sommets est l'union disjointe de ces couches . La ème couche est , la première couche est l'ensemble des voisins de , la deuxième couche est l'ensemble des sommets dont la distance à est de deux, et ainsi de suite. L'algorithme BFS visite les sommets du graphe dans un ordre particulier - couche par couche. Chaque couche couvre toute la largeur, mais les différentes couches sont à des profondeurs différentes.k a k a (k≥0) 0 {a} a a
D'autre part, l'algorithme DFS explorerait aussi profond que possible dans une direction (c. -à visiter premier voisin de, puis son voisin, puis son voisin, et ainsi de suite) avant de revenir à et la visite du voisin inexploré de . Cet algorithme va d'abord en profondeur, au lieu de visiter les voisins en profondeur.a a a
Ainsi, DFS et BFS diffèrent dans l'ordre dans lequel ils visitent les sommets.
la source