Updated March 22, 2023
Difference Between BFS and DFS
Breadth-First Search(BFS) and Depth First Search(DFS) are two important algorithms used for searching. Breadth-First Search starts its search from the first node and then moves across the nearer levels to the root node while the Depth First Search algorithm starts with the first node and then completes its path to the end node of the respective path. Both the algorithms traverse through every node during the search. Different codes are written for the two algorithms to execute the process of traversing. They are also considered as important search algorithms in Artificial Intelligence.
In this topic, we are going to learn about BFS VS DFS.
How BFS and DFS work?
The working mechanism of both algorithms is explained below with examples. Please refer to them for a better understanding of the approach used.
Breadth-First Search Example
- Step 1: N1 is the root node so that it will start from here. N1 is connected with three nodes N2, N3, and N4. All three nodes are not visited yet. So, we start from N2 and store it in the queue. So, the queue named Q contains only N2.
Q: N2
- Step 2: Next the node which is connected to N1 is N3. Since we went across or visited the node, we will store it in the queue. So, the updated queue is
Q: N3, N2
- Step 3: Next the node which is connected to the root node is N4. We will store it in the queue.
Q: N4, N3, N2
- Step 4: All the nodes that are connected to N1 are stored in the queue. Now, we remove N2 from the queue as per First in First Out principle(FIFO) and find the nodes that are connected to the N2, i.e. N5. N5 is not visited once so that we will store it in the queue.
Q: N5, N4, N3
- Step 5: All the vertices are visited, so we remove the nodes from the queue until it is empty.
Depth First Search Example
- Step 1: We will start with N1 as the starting node and store it in a stack S. N1 is connected with three neighbouring nodes N2, N3 and N4. Starting with N2 (you can start alphabetically or numerically), we will put this in the stack.
S: N2(Top), N1
- Step 2: Now, the neighbouring nodes of N2 are N1 and N5. Since N1 is already present in the stack that means it is visited, so we will take N5 and put it in stack S.
S: N5(Top), N2, N1
- Step 3: Now, the neighbouring nodes of N5 are N3 and N4. We will N3 and put it in the stack.
S: N3(Top), N5, N2, N1
Now N3 is connected to N5 and N1 which are already present in the stack that means they are visited to remove N3 from the stack as per Last in First Out principle (LIFO) principle.
S: N5(Top), N2, N1
- Step 4: Now, we will put the last node, which was we did not come across in the whole traversing in N4 and put it in the stack.
S: N4(Top), N5, N2, N1
- Step 5: Now we are not left out with any other nodes, so we will check in the stack if there are any nodes connected to the respective nodes present in it that are not visited. If all the connected nodes are visited, then we will remove the nodes present in the stack. For example, N4 has no connecting nodes that we did not check to remove it from the stack. Similarly, we can check for other nodes. The algorithm stops once the stack is empty.
Head to Head Comparison Between BFS and DFS (Infographics)
Below are the top 6 differences between BFS VS DFS
Key Differences Between BFS and DFS
Let us discuss some of the major key differences between BFS vs DFS.
- Breadth-First Search(BFS) starts from the root node and visits all the respective nodes attached to it while DFS starts from the root node and completes the full path attached to the node.
- BFS follows the approach of Queue while DFS follows the approach of Stack.
- The approach used in BFS is optimal while the process used in DFS is not optimal.
- If our objective is to find the shortest path than BFS is preferred over DFS.
BFS and DFS Comparison Table
Let’s discuss the top comparison between BFS vs DFS.
| BFS | DFS |
| The full form of BFS is Breadth-First Search. | The full form of DFS is Depth First Search. |
| BFS is meant to find the shortest distance, and it starts from the first or root node and moves across all its nodes attached to the respective nodes. You can get a clear view of its working mechanism after going through the below example. | DFS follows a depth-based approach, and it completes the full path through all the nodes attached to the respective node. You can get a clear view of its working mechanism after going through the below example. |
| It is done using the Queue principle, the First In First Out approach(FIFO). | It is done using the Stack principle, the Last In First out approach(LIFO). |
| The nodes which are traversed more than once are removed from the queue. | The visited nodes are inserted into the stack, and later if there are no more nodes to be visited, they are removed. |
| It is comparatively slower than Depth First Search. | It is faster than the Breadth-First Search algorithm. |
| Memory allocation is more than the Depth First Search algorithm. | Memory allocation is comparatively less than the Breadth-First Search Algorithm. |
Conclusion
There are many applications where the above algorithms are used as machine learning or to find artificial intelligence-related solutions etc. They are mainly used in graphs to find whether it is bipartite or not, to detect cycles of connected components. They are also considered as important algorithms in finding the path or finding the shortest distance. Depending on the requirements of the business, we can use two algorithms. However, Breadth-First Search is considered an optimal way rather than the Depth First Search algorithm.
Recommended Articles
This is a guide to BFS VS DFS. Here we discuss the BFS VS DFS key differences with infographics and comparison table. You may also have a look at the following articles to learn more –
