Breadth-Search Algorithm?

1

Hello, Can anyone here help me with the term Breadth-Search Algorithm in AI? What is it?

2

never heard of Breadth search, do you mean Breadth first search?

3

Uhuh, i never heard before of this ‘Breadth-first search’ ^^
After reading this post among the others i randomly chose a video from the fcc channel just to have an overview of what the video looks like while ending my coffee.
Guess what popped out? :smile:

Data structures and Algorithms in Javascript : 1:46:46

4

Breadth first search and depth first search are very common algorithm for traversing trees and graphs. It’s not something you encounter as a beginner but it’s rather fundemental. In fact, it’s common to see tree/graph traversal questions in coding interviews

5

Imagine you have a tree like this:

        A
        |
   +----+---+
   |    |   |
   B    C   D
   |    |
   E    F

In a depth-first traversal, you’d visit nodes A, B, then E, then C and F, then D. Notice how you go try to go “down” the tree before you go “across” it. That’s why it’s called “depth-first”. In breadth-first, you go across before down, so you’d visit the nodes A, B, C, D, E, then F.

If you search Wikipedia for “Breadth First Search”, you can watch an animated example of BFS in action (it’s the second diagram down, on the right)

2 Likes
6

Basically, we need to start the root node search. And proceed first through neighboring nodes. In addition, it moves to the next level of nodes. In addition, it generates one tree at a time until the solution is found. This search can be carried out using the data structure of the FIFO queue. This method provides the solution with the shortest path. FIFO (first in the beginning). If the ramification factor (average number of child nodes for a particular node)= b and depth= d, the number of nodes at level d= bd. In the worst case the total number of nodes created is b + b2 + b3 + … + bd.

1 Like