DEV Community

loading...
Cover image for Breadth First search and Depth First Search
Mozilla Club of UCSC

Breadth First search and Depth First Search

ashfaq1998data profile image Mohammed Ashfaq Ashar ・5 min read

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

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

Step 2

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

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

Step 4

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

Step 5

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

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

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

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

Step 1

  • First of all, let's create a stack Alt Text

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

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

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

Step 5

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

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

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

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!

Discussion (0)

pic
Editor guide