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.

Solution 1

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

Here 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.

---

The recursive implementation looks like

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

The recursion ends when you reach a node that has no children, so it is guaranteed to end for finite, acyclic graphs.

---

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 (use the "Alternate time" line above instead of the first "Work" line), and not too hard if you use a explicit stack, but I'll leave it as an exercise.

Solution 2

Understanding the terms:

This picture should give you the idea about the context in which the words breadth and depth are used.

---

Depth-First Search:

• Depth-first search algorithm acts as if it wants to get as far away from the starting point as quickly as possible.

• It generally uses a Stack to remember where it should go when it reaches a dead end.

• Rules to follow: Push first vertex A on to the Stack

  1. If possible, visit an adjacent unvisited vertex, mark it as visited, and push it on the stack.
  2. If you can’t follow Rule 1, then, if possible, pop a vertex off the stack.
  3. If you can’t follow Rule 1 or Rule 2, you’re done.

• Java code:

  public void searchDepthFirst() {
      // Begin at vertex 0 (A)
      vertexList[0].wasVisited = true;
      displayVertex(0);
      stack.push(0);
      while (!stack.isEmpty()) {
          int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
          // If no such vertex
          if (adjacentVertex == -1) {
              stack.pop();
          } else {
              vertexList[adjacentVertex].wasVisited = true;
              // Do something
              stack.push(adjacentVertex);
          }
      }
      // Stack is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++)
          vertexList[j].wasVisited = false;
  }
  

• Applications: Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.

---

Breadth-First Search:

• The breadth-first search algorithm likes to stay as close as possible to the starting point.
• This kind of search is generally implemented using a Queue.
• Rules to follow: Make starting Vertex A the current vertex
  1. Visit the next unvisited vertex (if there is one) that’s adjacent to the current vertex, mark it, and insert it into the queue.
  2. If you can’t carry out Rule 1 because there are no more unvisited vertices, remove a vertex from the queue (if possible) and make it the current vertex.
  3. If you can’t carry out Rule 2 because the queue is empty, you’re done.

• Java code:

  public void searchBreadthFirst() {
      vertexList[0].wasVisited = true;
      displayVertex(0);
      queue.insert(0);
      int v2;
      while (!queue.isEmpty()) {
          int v1 = queue.remove();
          // Until it has no unvisited neighbors, get one
          while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
              vertexList[v2].wasVisited = true;
              // Do something
              queue.insert(v2);
          }
      }
      // Queue is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++) 
          vertexList[j].wasVisited = false;
  }
  

• Applications: Breadth-first search first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex.

Hopefully that should be enough for understanding the Breadth-First and Depth-First searches. For further reading I would recommend the Graphs chapter from an excellent data structures book by Robert Lafore.

Solution 3

Given this binary tree:

Breadth First Traversal:
Traverse across each level from left to right.

"I'm G, my kids are D and I, my grandkids are B, E, H and K, their grandkids are A, C, F"

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

Depth First Traversal:
Traversal is not done ACROSS entire levels at a time. Instead, traversal dives into the DEPTH (from root to leaf) of the tree first. However, it's a bit more complex than simply up and down.

There are three methods:

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

Usage (aka, why do we care):
I really enjoyed this simple Quora explanation of the Depth First Traversal methods and how they are commonly used:
"In-Order Traversal will print values [in order for the BST (binary search tree)]"
"Pre-order traversal is used to create a copy of the [binary search tree]."
"Postorder traversal is used to delete the [binary search tree]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

Solution 4

I think it would be interesting to write both of them in a way that only by switching some lines of code would give you one algorithm or the other, so that you will see that your dillema is not so strong as it seems to be at first.

I personally like the interpretation of BFS as flooding a landscape: the low altitude areas will be flooded first, and only then the high altitude areas would follow. If you imagine the landscape altitudes as isolines as we see in geography books, its easy to see that BFS fills all area under the same isoline at the same time, just as this would be with physics. Thus, interpreting altitudes as distance or scaled cost gives a pretty intuitive idea of the algorithm.

With this in mind, you can easily adapt the idea behind breadth first search to find the minimum spanning tree easily, shortest path, and also many other minimization algorithms.

I didnt see any intuitive interpretation of DFS yet (only the standard one about the maze, but it isnt as powerful as the BFS one and flooding), so for me it seems that BFS seems to correlate better with physical phenomena as described above, while DFS correlates better with choices dillema on rational systems (ie people or computers deciding which move to make on a chess game or going out of a maze).

So, for me the difference between lies on which natural phenomenon best matches their propagation model (transversing) in real life.

View more solutions

Comments

[rmeador]

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

[jonnybazookatone]

I had that thought also, but then the examples given are slightly nicer than those found on wikipedia....

[Guy Coder]

See this visual example. While I would like to post this as answer, since it is a link only it would get down votes, thus a comment.

[batbrat]

@dmckee Thanks! I believe you meant "Work on the payload at Node," right?

[Theraot]

It may worth noting that you can modify the depth-first version to get prefix (A, B, D, C, E, F - the first one presented), infix (D, B, A, E, C, F - used for sorting: add as an AVL tree then read infix) or postfix (D, B, E, F, C, A the alternative presented) traversal. The names are given by the position in which you process the root. It should be noted that infix only really makes sense for binary trees. @batbrat those are the names... given the time since you asked, you probably already know.

[batbrat]

@Theraot thanks for adding that in! Yes, I do know about these kinds of traversals and why Infix makes sense only for binary trees.

[IgorGanapolsky]

How to decide which solution has a better space or time complexity?

[dmckee --- ex-moderator kitten]

@IgorGanapolsky Should be the same for both on principle (after all, they use essentially the same code). A more interesting question would be how they impact the cache and working set, but I think that will depend on the morphology of the tree.

[Soner from The Ottoman Empire]

Were I to have ten more voting up right, I would do so.

[juanmf]

You can implement them with a similar algorithm, just use stack for DFS and queue for BFS. The problem with BFS is that you need to keep track of all nodes seen so far. DFS in physics.. I imagine alternative universes and you want one with life, all children of root, are different big-bangs and you go all the way down to the universe death, no life? you go back to the last bifurcation and try another turn, until all are exhausted and you go to the next big-bang, setting new physical laws for the new universe. super intuitive. a good problem is finding a way with the horse in a chess board.

[Snow]

@snr you could award a bounty ;)

[Soner from The Ottoman Empire]

@Snow if you tell its directives, I can. I don't know how to do.

[Yogesh Umesh Vaity]

Thank you @snr, I'm so pleased to receive my first bounty. I appreciate a lot.

[Yogesh Umesh Vaity]

Thanks @Snow, I'm glad you guys found my answer useful.

[dreftymac]

@YogeshUmeshVaity Excellent answer -- this is a classic example of a well-explained top-tier StackOverflow/StackExchange reply. id="dmid://uu745gurulevel1622917502"

[mcvkr]

I was willing to award a bounty but the author is much richer than me 🤤

[Yogesh Umesh Vaity]

@mcvkr, no worries. I'm flattered just by the fact that you considered the answer worth awarding a bounty.