EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial BFS VS DFS
 

BFS VS DFS

Priya Pedamkar
Article byPriya Pedamkar

Updated March 22, 2023

BFS vs DFS

 

 

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.

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

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

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

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

BFS-vs--DFS-info

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 –

  1. BFS Algorithm
  2. Teradata vs Oracle
  3. Big Data vs Data Warehouse

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - ENROLL NOW