Distinguishing BFS and DFS

Breadth First Search and Depth First Search in Python

While studying Graphs in Computer Science, the use of Breadth First Search versus Depth First Search was a popular topic. To help myself and others, I have outlined the difference between the search tools, as well as defining Stacks and Queues (another tool when creating Graphs).

Picture credit to https://res.cloudinary.com/practicaldev/image/fetch/s---f65OlYQ--/c_imagga_scale,f_auto,fl_progressive,h_420,q_auto,w_1000/https://dev-to-uploads.s3.amazonaws.com/i/e2ru41fjhqs4ombbcedf.png

Let’s start with BFS. BFS is meant to find the shortest path in a graph. I like to visualize a lung taking in air. The search is wide, starts from the top, and slowly works it’s way down to the last node/vertex in a graph. One node is selected at a time, marked as “visited”, then the adjacent nodes are visited and will be stored in a Queue. A queue is a linear data structure that follows a “First In First Out” order, removing the least recently added node.

For the example above, the output will be [A,B,C,D,E,F]. To better understand, I will share BFS and Queue in Python below. Sometimes it helps to see the code layout as well.

Code found here

Now let’s talk about Depth First Search (DFS). DFS is different from BFS, as the search starts at a node and traverses the branch as far as possible before backtracking and then expanding to other nodes. For DFS, I imagine straight lines running through the graph. For the above graph example, it would output [A,B,D,E,C,F]. Instead of a Queue, DFS utilizes the Stack data structure, which is “Last In First Out” or “First In Last Out”. Here is a code example to help understand.

I hope this was helpful in deciphering the difference between a breadth first search and depth first search technique in Graphs. Feel free to take a look at my Github here for more helpful code when learning about Graphs!