Difference between DFS and BFS

Distinguish between DFS and BFS

Here we will learn about the difference between DFS and BFS.

Features BFS DFS
1. Stands for Breadth-First Search Depth-First Search
2. Data structure uses a queue data structure Uses stack data Structure
3. Principle FIFO (First in first out) LIFO (Last in First out)
4. Time Complexity for BFS O(V+E)

where V is vertices and is Edges

for DFS O(V+E)

where V is vertices and E is edges.

5. Traversal order Level order Traversal Depth
6. Traversal tree Narrow and long Wide and short
7. Backtracking No need for backtracking in BFS Need of backtrace king in DFS
8. pathways Always finds the easiest path for a destination First goes to the bottom of the subtree and then backtrack

 

Depth-First Search (DFS)

DFS works in two stages, Firstly it visited vertices and placed them in the visited list and other adjacent vertices are stored in the stack.

Example for DFS

Following is the example with an undirected graph, with 5 vertices

Difference between BFS and DFS

Step 1:

In first step algorithm starts with vertex 0, it starts with placing the visited 0 zero in the visited list and other adjacent vertices in the stack.

 

Step 2:

In the second step, It visited vertex 1 so it placed it in the visited list and its other adjacent vertices in the stack.

Step 3:

In the third step, it visited vertex 2 so placed that vertex in the visited list and its adjacent vertex in the stack.

Step 4:
In the fourth step, it visited vertex 4 before 3 because it is adjacent to vertex 2 and placed it in the visited list and the remaining vertex in the stack.

Difference between BFS and DFS

Step 5:

In the last step, it visited the remaining vertex and placed it in the visited list.

Difference between BFS and DFS

 

Breadth-First Search (BFS)

BFS algorithm selects any node as an initial node and marks it as visited, then it finds it’s another adjacent node that is unvisited.

Then it moves further towards the unvisited node and analyzes it.

Graph for BFS

Difference between BFS and DFS

In the above diagram, we learned about how BFS works in 3 levels, starting with level 0 to level 2.

 

Key Difference between DFS and BFS

  1. BFS traverse according to tree level however DFS traverse according to tree depth.
  2. In BFS there is no need for backtracking but in DFS backtracking always takes place.
  3. The traversal tree for BFS is Narrow and long and for DFS it is wide and short.
  4. But the time complexity of both algorithms is the same.

 

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *