Differences between Depth-First-Search and Breadth-First Search

1. In General:
The key difference between depth first search and breadth first search is the the order of visiting each nodes in a graph.

In breadth first search, we start at a node, called root, visiting its all immediate neighbors before moving to another node. After moving to another node, we also trying ti discover all of its neighbors and so on. In other words, we are trying to go as WIDE as possible. We keep doing this until we have no node left to visit.

In depth first search, however, we start at a node and traverse as far as possible along the branch before recursing back to the original node. In other words, we are trying to go as DEEP as possible from the root.

2. Implementation
Implementation-wise, the breadth first search uses a queue to keep track of the nodes visited. Depth first search, on the other hand uses a stack.

In depth first search, we mark a node as visited when we pop it from the stack, NOT when we push it into the stack..

Suppose we have a graph:

If we mark the nodes as visited when we pop it from the stack:

The order of the nodes we visit will be: A B D H E C F G. Note that we push the node into the stack from right to left (We push C before B and push E before D).

READ  CSS Sprites Generator and Rmagick

However, if we mark the node as visited when we push it into the stack as the following code:

The order of nodes visited will be: A C B E D H G F, which is not depth first search.

This is a big difference from breadth first search: Whether we mark a node as visited when we push that node into the queue or when we remove from the queue doesn’t matter. This time we push the node into the queue from left to right.

The order of visiting is: A B C D E G F H

Note: Depth first search has a recursive implementation, which implicitly use a stack.

In this implementation, we only mark a node as visited when we start exploring its neighbors, which is equivalent to the non recursive version.

READ  Online Income Report – How to Recover From a Sudden Drop in Google Rankings

Leave a Reply

Your email address will not be published. Required fields are marked *