Breadth-Search Algorithm?

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