Breadth First Vs Depth First

Question

When Traversing a Tree/Graph what is the difference between Breadth First and Depth first? Any coding or pseudocode examples would be great.

Answer 1

Did you check wikipedia (depth first, breadth first)? There are code examples on those pages, along with lots of pretty pictures.

Answer 2

This link helped me when I was learning about it.

Animation helps to visualize. Breadth First Search/Depth First Search Animations

Answer 3

These two terms differentiate between two different ways of walking a tree.

It is probably easiest just to exhibit the difference. Consider the tree:

    A
   / \
  B   C
 /   / \
D   E   F

A depth first traversal would visit the nodes in this order

A, B, D, C, E, F

Notice that you go all the way down one leg before moving on.

A breadth first traversal would visit the node in this order

A, B, C, D, E, F

He we work all the way across each level before going down.

(Note that there is some ambiguity in the traversal orders, and I've cheated to maintain the "reading" order at each level of the tree. In either case I could get to B before or after C, and likewise I could get to E before or after F. This may or may not matter, depends on you application...)

---

Both kinds of traversal can be achieved with the pseudocode:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

The difference between the two traversal orders lies in the choice of Container.

• For depth first use a stack. (The recursive implementation uses the call-stack...)
• For breadth-first use a queue.

---

At this point, I've still cheated a little. With a little cleverness you can also work-on the nodes in this order:

D, B, E, F, C, A

which is a variation of depth-first, where I don't do the work at each node until I'm walking back up the tree. I have however visited the higher nodes on the way down to find their children.

This traversal is fairly natural in the recursive implementation, and not too hard if you use a explicit stack, but I'll leave it as an exercise.

Answer 4

You can read my series of posts about Breadth and Depth First Search. It contains source code implementation in C#.

Take a look at my blog posts:

• Breadth and depth first search
• Breadth and depth first search - part 2
• Breadth and depth first search - part 3