Breadth First search and Depth First Search
Tags: algorithms, tutorial, graph, traversal
Published: 2020-12-23 04:43:16



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. 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/9wr9y35xq4z86u3505a7.png)

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
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/4yggn413ae3u943pyhjv.png)


**Step 2**
-	Select a starting node and colour it. For our easiness I have selected the element **“S”**
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/vsxr70u236zm059xwpt6.png)


**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
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/nz0fya2nfoqnj65pvxbb.png)

**Step 4**
-	Now the next element which is adjacent to **“S”** is **“B”**. So colour and insert it
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/cftdfhpn0xakce435pm0.png)

**Step 5**
-	Similarly, we can observe the next adjacent element of **“S”** is **“C”**. Colour and insert it
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/l4gdhfrbp50herwijiby.png)

**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”**
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/429qbdae7j3dhlkvzn5g.png)

**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
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/6p5cbf7aq0pcoxj3qj5x.png)

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.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/3prez4d7p4jznw5paezz.png)


**Step 1**
-	First of all, let's create a stack
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/lev1okqcawhnwo8jhfe9.png)

**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
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/5lbkxg0s5ef0s35ajh2o.png)

**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
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/mi4plzyaihngoc1gbo8r.png)

**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
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/aprq4u0wwremf0x544dw.png)

**Step 5**
-	Now adjacent element of **“D”** is **“B”**. So, we colour and put into stack
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/saigsnvtzzy4je1467di.png)

**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”**.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/qm01s5o2aizl2shkvevl.png)

**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. 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/yqgbit95q2ebvrwe2e6j.png)

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!