Breadth First search and Depth First Search

Today, we are discussing an interesting concept related to Data Structures and Algorithms that most of the computer science students face many difficulties in, which is Breadth First Search and Depth First Search also known as BFS and DFS respectively.

This tutorial for all the beginners who are facing difficulties related to the graph traversal algorithms. There are several graph traversal algorithms in Data structures and Algorithms, but in our discussion we will be discussing BFS and DFS. Additionally, I would like to give some important background information, so that you would have better foundation in this tutorial in order to further proceed with BFS and DFS.

Why do we need to have graph traversal algorithms?

Before we going further with what is BFS and DFS, it is must to have a clear understanding on why we need this traversal. Normally traversal is used to solve several problems inorder to increase the efficiency. Some examples are:

• Finding all the nodes which are reachable
• Finding the best reachable node
• Finding the best path through a graph And so on. The main goal of this type of graph traversal is to find all the nodes that are reachable from a given set of root nodes.

What is BFS and DFS?

Breadth First Search (BFS) traversal is mainly used to find the shortest path from a given graph. In order to perform the BFS, we need to implement the Queue Data Structure, which follows the principle of FIFO (First In First Out). I hope you all have clear idea of Queue Data structure.

Depth First Search (DFS) traversal mainly traverse the graph in a depthward motion. This traversal is used for cycle detection, strongly connected components and so on. We can implement DFS by using the Stack Data structure, which follows LIFO (Last In First Out) Principle.

Don’t worry, if you can’t understand the Stack and Queue Data Structure the examples in this article will give you a clear understanding on these data structures. Additionally, you will get a good knowledge in finding the BFS and DFS for a given graph.

Finding the BFS for the given graph

Now we have started a more interesting concept that is how to find the BFS for a given graph.

Let's consider the simple graph given above. This problem is solved by breaking our problem into several steps.

Step 1

• Initialize a queue. We insert the element in the rear end of the queue and remove the element from the front end

Step 2

• Select a starting node and colour it. For our easiness I have selected the element “S”

Step 3

• Now, we select the adjacent node of “S”, which is not coloured. According to our example, we can see A, B and C are adjacent of S and not coloured. So, I select “A”. And insert into queue and colour it

Step 4

• Now the next element which is adjacent to “S” is “B”. So colour and insert it

Step 5

• Similarly, we can observe the next adjacent element of “S” is “C”. Colour and insert it

Step 6

• Now we can see there is no further visited nodes of “S”. So, we can remove element. You know that Queue follows FIFO. So, the element to remove is “A”

Step 7

• Now we can see only a single adjacent node of “A” which is not visited. So colour it and insert it So finally, we can see there are no further nodes to colour. So, remove all the elements one by one

So, the BFS of the graph is

S, A, B, C, D

I hope you have gotten a better idea in finding the BFS, and also, I hope that now you can solve any type of BFS problem.

Now let us look at how to find the DFS for the given graph

Finding the DFS for the given graph

Similarly, as I explained how to find the BFS, I will help to find the DFS in most simple manner by using the same graph.

But as I explained before, to implement DFS, we need the Stack data structure. As you all aware that the Stack follows LIFO which is Last In First Out Principle.

Step 1

• First of all, let's create a stack

Step 2

• You can select whatever node as the starting node. As the previous example in BFS, I have taken “S” as the Starting node. Here too I am taking “S” as my starting node. Colour it and put it into stack

Step 3

• Now we can see there are 3 adjacent uncoloured nodes, As for our easiness I select “A” next node, colour it and put it into stack

Step 4

• Now we can see top element is “A”. So now we have to select adjacent element of “A”. Since “D” is the only adjacent element, we colour it and put into stack

Step 5

• Now adjacent element of “D” is “B”. So, we colour and put into stack

Step 6

• As a next step, we couldn’t see any adjacent element of “B”. so, we simply remove it, so now top value is “D”.

Step 7

• So as a final step, we can observe the adjacent element of “D” is “C”, which is not coloured yet. So, we colour it and put into stack. Now “C” doesn’t have any uncoloured nodes. So, we repeatedly remove the nodes from stack, until we find any uncoloured nodes.

So as a result, The DFS of the above graph is
S, A, D, B, C

From above explanation, I hope that you have gained a clear understanding on BFS and DFS. I kindly request you all to go through this tutorial very carefully along with the images.

Hope to see you soon with my next article!