Difference between Depth first search and Breadth first search algorithm

Question

Currently I am studying Depth first search algorithm and Breadth first search algorithm. Both these algorithms are looking quite similar to me except for some differences. In BFS, we start with a vertex and then group all the vertices adjacent to it. Then we go alphabetically or in numeric order to construct a path. In DFS, we don't do any grouping. We just keep backtracking and visiting new vertices until there are none left.

This difference seems a minor one to me. Is/are there any other differences in between these to search algorithms? It would be better if it can be explained through an example.

Answer 1

Both DFS and BFS are essentially the same algorithm that expand and visit vertices in some order, but differ in the way they store these vertices, which impacts this order. Hence, differ in their internal data-structure. DFS uses a stack where as BFS uses a queue, which means DFS explores newly discovered vertices first (LIFO) and BFS explores adjacent vertices first (FIFO).

The impact of this can be noticed if you think about them as files and directories in a computer. If you had the following directories:

C:\
   -> Documents
   -> Program Files
       -> Firefox
           -> ff.exe
       -> Chrome
           -> chrome.exe
   -> Users
       -> Downloads
           -> paper.txt
       -> Music
           -> song.mp3

What DFS does it it keeps going through directories till it cannot go any further, and then backtracks. So DFS applied to the above example would give:

C:\Documents
C:\Documents\ (empty, backtrack)
C:\Program Files
C:\Program Files\
C:\Program Files\Firefox
C:\Program Files\Firefox\ff.exe (backtrack)
C:\Program Files\Chrome
C:\Program Files\Chrome\chrome.exe (backtrack)
...

BFS expands directories as follows:

C:\Documents
C:\Program Files
C:\Users
C:\Documents\ (empty)
C:\Program Files\Firefox\
C:\Program Files\Chrome\
C:\Program Files\Firefox\ff.exe
C:\Program Files\Chrome\chrome.exe
...

Hope that helps.

Edit: You can also look at the following link (I put it here because I cannot comment - yet): https://stackoverflow.com/questions/687731/breadth-first-vs-depth-first

Answer 2

Suppose the starting vertex is $r$.

• BFS visits vertices in the order of non-decreasing distance to $r$. In other words, for two vertices $u$ and $v$, if the distance between $u$ and $r$ is smaller than that between $v$ and $r$, $u$ will be visited before $v$. Here, we assume the graph is unweighted (i.e., the edge weight is 1) and distance between two vertices is defined to be the length of shortest path between two vertices.

• DFS does not visit vertices according to their distances to $r$. It goes as deeply as possible. In other words, when a vertex $u$ is being visited, and if $u$ has a non-visited-yet neighbor $v$, DFS will visit $v$ (or some other non-visited-yet $u$'s neighbor) next.

On implementation, a data structure called "queue" is usually used to implement BFS, while DFS usually employs a structure called "stack".