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
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.
Step 5:
In the last step, it visited the remaining vertex and placed it in the visited list.
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
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
- BFS traverse according to tree level however DFS traverse according to tree depth.
- In BFS there is no need for backtracking but in DFS backtracking always takes place.
- The traversal tree for BFS is Narrow and long and for DFS it is wide and short.
- But the time complexity of both algorithms is the same.