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.
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.
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.
Let's consider the simple graph given above. This problem is solved by breaking our problem into several steps.
- Initialize a queue. We insert the element in the rear end of the queue and remove the element from the front end
- Select a starting node and colour it. For our easiness I have selected the element “S”
- 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
- Now the next element which is adjacent to “S” is “B”. So colour and insert it
- Similarly, we can observe the next adjacent element of “S” is “C”. Colour and insert it
- 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”
- 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
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.
- First of all, let's create a stack
- 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
- 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
- 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
- Now adjacent element of “D” is “B”. So, we colour and put into stack
- As a next step, we couldn’t see any adjacent element of “B”. so, we simply remove it, so now top value is “D”.
- 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!